优先队列堆：修复 bubbleDown 方法

Question

我正在研究优先级队列（堆），我认为我有很好的基础。我认为我的方法大部分都有意义，但在我的 bubbleDown 和 deleteMin 方法上确实很吃力。

public class Heap {
    private int n;
    private Node[] s;

    public Heap() {
        s =  new Node[128];
        n =0;
    }

    public boolean isEmptySet() {
        return (n == 0);
    }   

    public Node findMin() {
        return s[0];
    }

    public void insert(Node p) {
        s[n] = p;
        n = n+1;
        bubbleUp(n - 1); // needs to subtract 1 because we do the addition
        }

    public void bubbleUp(int index) {
        if (index == 0) {
            return index;
        }

        else if (index > 0) {
            int parentIndex = (index - 1) / 2; // Might not need to subtract 1
            if (s[index].getKey() < s[parentIndex].getKey()) {
                swapNode(index, parentIndex);
                bubbleUp(parentIndex);
            }
        }
    }

    public void swapNode(int index, int parentIndex) {
        Node temp = s[index];
        s[index] = s[parentIndex];
        s[parentIndex] = temp;
    }

    public void deleteMin(Node p) {
        n = n - 1;
        bubbleDown(s[0], s[n]);
        return s[n];
    }


    public void bubbleDown(int index) {
        if (index < 0) {
            int leftChildIndex = (i*2) + 1;
            int rightChildIndex = (i*2) + 2;
            if (s[index].getKey() > s[leftChildIndex].getKey()) {
                swapNode(index, leftChildIndex);
                bubbleDown(leftChildIndex);
            } else if (s[index].getKey() < s[leftChildIndex].getKey() && s[index].getKey() > s[rightChildIndex].getKey()) {
                swapNode(index, rightChildIndex);
                bubbleDown(rightChildIndex);
            }
        }
    }
}

Answer 1

首先，在您的 bubbleUp() 中，您确实需要减去 1 才能找到 parent。考虑到 0 的 children 是 1 和 2。如果您在除法之前没有减去 1，那么 2 的 parent 将被错误地计算为 1。

在您的 findMin() 中，您应该在盲目返回根项之前检查是否有空堆。我知道你有一个 isEmptySet() 函数，但是如果你为空堆调用它 findMin() 应该抛出异常。

现在，在你的 deleteMin() 和 bubbleDown() 上。 deleteMin 应该是：

public void deleteMin(Node p){
    n = n - 1;
    // place root node at the end of the heap,
    // and the last node at the root.
    swapNode(0, n);

    // adjust the heap
    bubbleDown(0);
    return s[n];
}

按照您的方式，deleteMin 将节点而不是节点索引传递给 bubbleDown，并且当 bubbleDown 只接受一个参数时它传递了两个参数。

您的 bubbleDown 方向是正确的，但您必须小心。向下冒泡的规则是，如果该节点大于其 children 中的任何一个，则将节点与两个 children 中最小的节点交换。而且你不能盲目检查两个潜在的 children，因为节点可能根本没有 children。所以：

public void bubbleDown(int index){
    int childIndex = (index * 2) + 1;
    if (childIndex > n)
    {
        // if the first child index is off the end of the heap
        // then the item has no children. (It's a leaf.)
        return;
    }

    // first find the smallest child
    // This test is to prevent checking a right child that doesn't exist.
    if (childIndex < n)
    {
        if (s[childIndex] > s[childIndex+1])
        {
            childIndex = childIndex + 1;
        }
    }

    // childIndex holds the index of the smallest of the node's children.
    // swap if the parent is larger than the smallest child,
    // and then keep bubbling down.
    if (s[index] > s[childIndex])
    {
        swapNode(index, childIndex);
        bubbleDown(childIndex);
    }
}

优先队列堆：修复 bubbleDown 方法

Priority Queue Heap: fixing bubbleDown method

java

heap

priority-queue