使用二叉树实现堆

Question

之前在Stack Exchange中已经提出过这个问题,但是没有得到答复.

链接到前面提到的问题: 二进制堆通过二叉树结构实现

如何在二叉树中实现堆.要实现堆,了解最后一个填充节点和第一个未占用节点非常重要.这可以在树的级别排序中完成,但是时间复杂度将是O(n)以便找到第一个未占用的节点.那么,如何在O(logn)中的二叉树中实现堆？

谢谢Shekhar

Answer 1

要使用具有O(log n)时间复杂度的二叉树实现堆,您需要将节点总数存储为实例变量.

假设我们有10个总节点的堆.

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

我们将节点总数增加1.现在我们有11个节点.我们将新的节点总数(11)转换为其二进制表示:1011.

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

我们检查了每个级别一个节点,使得时间复杂度为O(log n)

Answer 2

您将不执行堆在二叉树,因为堆是一个二叉树.堆维护以下顺序属性 - 给定节点V,其父级大于或等于V.此外,堆是完整的二叉树.我在uni有ADS课程所以我会在答案的后面给你用Java实现堆.只列出您获得的主要方法复杂性:

• 尺寸()O(1)
• isEmpty()O(1)
• insert()O(logn)
• removeMin()O(logn)
• min()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:这是完成max logn times,其中n是节点数.这就是登录性能.

对于删除部分 - 您只能删除min - 最高节点.所以当你删除它时 - 你必须将它与最后一个节点交换 - 但是你必须维护堆属性而你必须做一个downHeapBubble().如果节点大于它与最小节点的子交换,依此类推,直到您没有留下任何子节点或者您没有较小的子节点.这可以在最大logn时间完成,因此这里有登录性能.您可以通过查看二进制树图片来解释自己为什么可以通过最大日志时间完成此操作

Answer 3

使用树实现堆

我正在回答我自己的需要 O(log n) 的问题，但限制是保留一个指向父级的指针。如果我们不保留指向父级的指针，我们大约需要 O(n)。我发布了这个问题以获得 O(log n) 的解决方案

以下是计算下一个未占用叶子的步骤（我们有一个指向父节点的指针）：

x = last inserted node. We save this after every insertion.
y = tmp node
z = next unoccupied node (next insertion)
   if x is left child
      z = x -> parent -> rightchild (problem solved.. that was easy)
   else if x is right child
      go to x's parent, until parent becomes left child. Let this node be y
      (subtree rooted at y's sibling will contain the next unoccupied node)
      z = y -> parent -> right -> go left until null

这是 O(log n)，但需要一个指向父级的指针。

O(n) 解决方案非常简单，只需对树进行级别排序，然后我们就可以得到下一个未占用节点的位置。

我的问题是：如何在不使用父指针的情况下在 O(log n) 中定位下一个未占用的节点。

谢谢。