如何实现在 D 堆优先级队列中查找最小子级的方法

Question

我在为分配从头创建的优先级队列类中有一个remove方法。我创建的优先级队列保存在一个数组中，索引从0开始。我跟踪等于数组长度的大小。remove方法使用名为的助手方法：

public int findSmallest(int parent)

其中parent是数组中存储父元素的位置，我希望返回其最小的子元素。顺序就是每个非叶子节点的子节点数。我发现最小的代码:

public int findSmallest(int parent) {
    int child = parent * order + 1;
    int smallest = child;
    for (int i = child; i < order + child; ++i) {
        if (size >= i) {
            return child;
        }
        if (queue[i].priority <= queue[smallest].priority) {
            smallest = child;
        }
    }
    return child;
}

它目前是我创建的PriorityQueue类的数组越界异常完整实现：

import java.util.*;

public class PriorityQueue {

    private class Item {
        private int priority;
        private Object data;

        private Item(int p, Object d) {
            priority = p;
            data = d;
        }
    }

    private Item queue[];
    private int order;
    private int size;

    public PriorityQueue(int ord, int s) {
        queue = new Item[s];
        order = ord;
        size = 0;
    }

    public int getPriority() {
        if (size > 0) {
            return queue[0].priority;
        }

        // -55 signifies that the queue is empty

        return -55;
    }

    public Object getData() {
        if (size > 0) {
            return queue[0].priority;
        }
        return null;
    }

    public void remove() {

        if (empty() == true) {
            System.out.println("Queue is empty, there is nothing to remove.");
            return;
        }

        Item x = queue[size - 1];
        size--;
        int child = 1;
        int parent = 0;

        while (child <= size) {
            child = findSmallest(parent);
            for (int i = order * parent + 1; i < child + order; i++) {
                if (child < size && queue[i].priority < queue[child].priority)
                    child = i;
            }
            if (x.priority < queue[child].priority)
                break;
            else {
                parent = child;
                queue[(child - 1) / order] = queue[child];
                child = order * child + 1;
            }
        }
        queue[(child - 1) / order] = x;
    }

    public int findSmallest(int parent) {
        int child = parent * order + 1;
        int smallest = child;
        for (int i = child; i < order + child; ++i) {
            if (size >= i) {
                return child;
            }
            if (queue[i].priority <= queue[smallest].priority) {
                smallest = child;
            }
        }
        return child;
    }

    public int getSize() {
        return size;
    }

    public boolean full() {
        return size == queue.length;
    }

    public boolean empty() {
        if (size > 0) {
            return false;
        }
        return true;
    }

    public void insert(int p, Object d) {
        // 1. Create a new Item and add it to queue[size]
            // Somewhere store new node created as TEMP
        // 2. while loop
        // 3. check if node has parent
            // 4. if it does --> check if parent.priority > child.priority
                // 5. if yes, swap

        if (full() == true) {
            System.out.println("Queue is full, cannot add new node.");
            return;
        }

        queue[size] = new Item(p, d);
        sort();
        size++;

    }

    // Sort() swaps new child node with parents if child.priority < parent.priority

    public void sort() {

        int child = size;
        Item temp = queue[child];
        while ( child > 0 && queue[child].priority < queue[(child-1)/(order)].priority) {
            queue[child] = queue[(child-1)/order];
            queue[(child-1)/order] = temp;
            child = ((child - 1) / order);
        }
        queue[child] = temp;
    }



    public static void main(String[] args) {
            PriorityQueue p1 = new PriorityQueue(5, 100);
            PriorityQueue p2 = new PriorityQueue(6, 100);
            PriorityQueue p3 = new PriorityQueue(7, 100);

            int p = -1; //pointless initialization to keep the compiler happy
            p1.insert(0, new Integer(0));
            System.out.println("First insert");

            for (int i = 1; i < 100; i++)
                p1.insert(i, new Integer(i));

            for (int i = 0; i < 100; i++)
                p2.insert(i, new Integer(i));

            for (int i = 0; i < 100; i++)
                p3.insert(i, new Integer(i));

            System.out.println("First insert tests");

            System.out.print(p1.getPriority()+",");
            while (!p1.empty()) {
                p = p1.getPriority();
                Object d = p1.getData();
                p1.remove();
            }
            System.out.println(p);

            System.out.print(p2.getPriority()+",");

            while (!p2.empty()) {
                p = p2.getPriority();
                Object d = p2.getData();
                p2.remove();
            }
            System.out.println(p);

            System.out.print(p3.getPriority()+",");

            while (!p3.empty()) {
                p = p3.getPriority();
                Object d = p3.getData();
                p3.remove();
            }
            System.out.println(p);
            System.out.println("First Remove Test");

            for (int i = 100; i > 0 ; i--)
                p1.insert(i, new Integer(i));

            for (int i = 100; i > 0 ; i--)
                p2.insert(i, new Integer(i));

            for (int i = 100; i > 0 ; i--)
                p3.insert(i, new Integer(i));

            System.out.println("Second insert tests");

            System.out.print(p1.getPriority()+",");
            while (!p1.empty()) {
                p = p1.getPriority();
                Object d = p1.getData();
                p1.remove();
            }
            System.out.println(p);

            System.out.print(p2.getPriority()+",");

            while (!p2.empty()) {
                p = p2.getPriority();
                Object d = p2.getData();
                p2.remove();
            }
            System.out.println(p);

            System.out.print(p3.getPriority()+",");

            while (!p3.empty()) {
                p = p3.getPriority();
                Object d = p3.getData();
                p3.remove();
            }
            System.out.println(p);
            System.out.println("Second Remove Test");

            Random r1 = new Random(1000);
            while (!p3.full()) {
                p = r1.nextInt(200);
                System.out.print(p+",");
                p3.insert(p, new Integer(p));
            }
            System.out.println();

            while (!p3.empty()) {
                System.out.print(p3.getPriority()+",");
                Object d = p3.getData();
                p3.remove();
            }
            System.out.println();
            System.out.println("Third Remove Test");
    }
}

Main包括我测试代码的3种不同方式。

Answer 1

如果您的问题只是使用“查找最小方法”，则解决方案如下：

public int findSmallest( int parent ) {

    int smallestChild = -1;

    int firstChild = parent * order + 1;
    int lastChild = parent * order + order;

    int currentSmallestChild = firstChild;

    for ( int i = firstChild + 1; i <= lastChild; i++ ) {
        if ( i > size || queue[i] == null ) {
            break;
        }
        if ( queue[currentSmallestChild].priority > queue[i].priority ) {
            currentSmallestChild = i;
            smallestChild = i;
        }
    }

    return smallestChild;

}

如果没有最小的孩子，它将返回-1。这段代码可以改进，我这样写是因为我认为它更容易理解。让我知道它是否有效。