使用二叉树实现堆

要实现具有 O（log n） 时间复杂度的二叉树的堆，您需要将节点总数存储为实例变量。

假设我们有一个总共 10 个节点的堆。

如果我们要添加一个节点...

我们将节点总数递增一。现在我们总共有 11 个节点。我们将新的节点总数 （11） 转换为其二进制表示形式：1011。

使用总节点（1011）的二进制表示，我们摆脱了第一个数字。之后，我们使用 011 在树中导航至下一个位置以插入节点。0 表示向左移动，1 表示向右移动。因此，对于011，我们将向左，向右，向右走...这会将我们带到下一个要插入的位置。

我们检查了每个级别的一个节点，使时间复杂度为O（log n）

您不会实现堆 IN 二叉树，因为堆是二叉树。堆维护以下顺序属性 - 给定节点 V，其父节点大于或等于 V。此外，堆是完整的二叉树。我在uni上过ADS课程，所以我会在后面的答案中给你我在Java中实现的堆。仅列出您获得的主要方法复杂性：

• 尺寸（） O（1）
• isEmpty（） O（1）
• insert（） O（logn）
• removeMin（） O（logn）
• 最小值（） O（1）

这是我的文件：Heap.java

public class Heap<E extends Comparable<E>> {

    private Object S[];
    private int last;
    private int capacity;

    public Heap() {
        S = new Object[11];
        last = 0;
        capacity = 7;
    }

    public Heap(int cap) {
        S = new Object[cap + 1];
        last = 0;
        capacity = cap;
    }

    public int size() {
        return last;
    }

    //
    // returns the number of elements in the heap
    //

    public boolean isEmpty() {
        return size() == 0;
    }

    //
    // is the heap empty?
    //

    public E min() throws HeapException {
        if (isEmpty())
            throw new HeapException("The heap is empty.");
        else
            return (E) S[1];
    }

    //
    // returns element with smallest key, without removal
    //

    private int compare(Object x, Object y) {
        return ((E) x).compareTo((E) y);
    }

    public void insert(E e) throws HeapException {
        if (size() == capacity)
            throw new HeapException("Heap overflow.");
        else{
            last++;
            S[last] = e;
            upHeapBubble();
        }       
    }

    // inserts e into the heap
    // throws exception if heap overflow
    //

    public E removeMin() throws HeapException {
        if (isEmpty())
            throw new HeapException("Heap is empty.");
        else {
            E min = min();
            S[1] = S[last];
            last--;
            downHeapBubble();
            return min;
        }
    }

    //
    // removes and returns smallest element of the heap
    // throws exception is heap is empty
    //

    /**
     * downHeapBubble() method is used after the removeMin() method to reorder the elements
     * in order to preserve the Heap properties
     */
    private void downHeapBubble(){
        int index = 1;
        while (true){
            int child = index*2;
            if (child > size())
                break;
            if (child + 1 <= size()){
                //if there are two children -> take the smalles or
                //if they are equal take the left one
                child = findMin(child, child + 1);
            }
            if (compare(S[index],S[child]) <= 0 )
                break;
            swap(index,child);
            index = child;
        }
    }

    /**
     * upHeapBubble() method is used after the insert(E e) method to reorder the elements
     * in order to preserve the Heap properties 
     */
    private void upHeapBubble(){
        int index = size();
        while (index > 1){
            int parent = index / 2;
            if (compare(S[index], S[parent]) >= 0)
                //break if the parent is greater or equal to the current element
                break;
            swap(index,parent);
            index = parent;
        }       
    }

    /**
     * Swaps two integers i and j
     * @param i
     * @param j
     */
    private void swap(int i, int j) {
        Object temp = S[i];
        S[i] = S[j];
        S[j] = temp;
    }

    /**
     * the method is used in the downHeapBubble() method
     * @param leftChild
     * @param rightChild
     * @return min of left and right child, if they are equal return the left
     */
    private int findMin(int leftChild, int rightChild) {
        if (compare(S[leftChild], S[rightChild]) <= 0)
            return leftChild;
        else
            return rightChild;
    }

    public String toString() {
        String s = "[";
        for (int i = 1; i <= size(); i++) {
            s += S[i];
            if (i != last)
                s += ",";
        }
        return s + "]";
    }
    //
    // outputs the entries in S in the order S[1] to S[last]
    // in same style as used in ArrayQueue
    //

}

HeapException.java:

public class HeapException extends RuntimeException {
    public HeapException(){};
    public HeapException(String msg){super(msg);}
}

为您提供O（logn）性能的有趣部分是和方法。我很快就会补充一些关于它们的良好解释。downHeapBubble()upHeapBubble()

upHeapBubble()在将新节点插入堆时使用。因此，当您插入时，您将插入到最后一个位置，然后您需要调用如下所示：upHeapBubble()

last++;
S[last] = e;
upHeapBubble();

然后将最后一个元素与其父元素进行比较，如果父元素更大 - swap：这是完成的最大logn次数，其中n是节点数。因此，这就是 logn 性能。

对于删除部分 - 您只能删除最小值 - 最高节点。因此，当您删除它时 - 您必须将其与最后一个节点交换 - 但是您必须维护堆属性并且必须执行.如果节点大于它的子节点，则与最小的节点交换，依此类推，直到您没有任何子节点或您没有较小的子节点为止。这可以完成最大 logn 时间，因此这就是 logn 性能。您可以解释自己为什么可以通过查看此处的二叉树图片来完成此操作的最大登录时间downHeapBubble()