Java 使用二叉树实现堆

Implement Heap using a Binary Tree

提问by user2200660

This question has been asked before in Stack Exchange but it went unanswered.

这个问题以前在 Stack Exchange 中被问过，但没有得到解答。

Link to the previously asked question: Binary Heap Implemented via a Binary Tree Structure

链接到先前提出的问题： 通过二叉树结构实现的二叉堆

How do I implement heap in a binary tree. To implement heap, it is important to know the last filled node and the first unoccupied node. This could be done in level ordering of the tree, but then the time complexity will be O(n) just to find the first unoccupied node. So, how to implement heap in a binary tree in O(logn)?

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

Thanks Shekhar

谢谢谢哈尔

回答by Anton Belev

You won't implement the heap INbinary tree, because the heap is Abinary tree. The heap maintains the following order property - given a node V, its parent is greater or equal to V. Also the heap is complete binary tree. I had ADS course at uni so I will give you my implementation of the heap in Java later in the answer. Just to list the main methods complexities that you obtain:

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

• size() O(1)
• isEmpty() O(1)
• insert() O(logn)
• removeMin() O(logn)
• min() O(1)

• 大小（）O（1）
• isEmpty() O(1)
• 插入（）O（登录）
• removeMin() O(logn)
• 分钟（）O（1）

Here is my Heap.javafile:

这是我的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);}
}

The interesting part that gives you O(logn) performance is the downHeapBubble()and upHeapBubble()methods. I will add good explanation about them shortly.

为您提供 O(logn) 性能的有趣部分是downHeapBubble()和upHeapBubble()方法。我很快就会对它们进行很好的解释。

upHeapBubble()is used when inserting new node to the heap. So when you insert you insert in the last position and then you need to call the upHeapBubble()like that:

upHeapBubble()在向堆中插入新节点时使用。因此，当您插入时，您将插入到最后一个位置，然后您需要upHeapBubble()像这样调用：

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

Then the last element is compared against it's parent and if the parent is greater - swap: this is done max logn times where n is the number of nodes. So here comes the logn performance.

然后将最后一个元素与它的父元素进行比较，如果父元素更大 - 交换：这样做最多 logn 次，其中 n 是节点数。所以这里是logn性能。

For the deletion part - you can remove only min - the highest node. So when you remove it - you have to swap it with the last node - but then you have to maintain the heap property and you have to do a downHeapBubble(). If the node is greater than it's child swap with the smallest one and so on until you don't have any children left or you don't have smaller children. This can be done max logn times and so here comes the logn performance. You can explain yourself why this operation can be done max logn times by looking in the binary tree pictures here

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

回答by Mario Rossi

Assuming you want to use a linkedbinary tree, with no pointers to parent nodes, then the only solution I can think of is keeping a counter of number of children in each node.

假设你想使用一个链接二叉树，没有指向父节点的指针，那么我能想到的唯一解决方案是在每个节点中保留一个子节点数的计数器。

availableLeaf(node) {
    if( node.left is Empty || node.right is Empty )
        return node ;
    else
       if( node.left.count < node.right.count )
           return availableLeaf(node.left)
       else
           return availableLeaf(node.right)
}

This strategy also balances the number of nodes on each side of each subtree, which is beneficial (though extremely slightly).

这种策略还平衡了每个子树每一侧的节点数量，这是有益的（尽管非常轻微）。

This is O(log n). Keeping track of count on insertion requires to come all the way up to the roof, but this doesn't change the O(lon n) nature of this operation. Similar thing with deletion.

这是 O(log n)。跟踪插入计数需要一直到屋顶，但这不会改变此操作的 O(lon n) 性质。与删除类似的事情。

Other operations are the usual, and preserve their performance characteristics.

其他操作是通常的，并保留其性能特征。

Do you need the details or prefer to work them out by yourself?

您需要详细信息还是更喜欢自己解决？

If you want to use a linked binary tree, with no other information than left and right pointers, then I'd suggest you to initiate a bounty for at least 100,000 points. I'm not saying it's impossible (because I don't have the math to prove it), but I'm saying that this has not been found in several decades (which I do know).

如果你想使用链接二叉树，除了左右指针没有其他信息，那么我建议你发起至少 100,000 点的悬赏。我并不是说这是不可能的（因为我没有数学来证明它），但我是说这几十年来还没有发现（我知道）。

回答by user2200660

HEAP IMPLEMENTATION USING TREE

使用树实现堆

I am answering my own question that takes O(log n), but the limitation is to keep a pointer to the parent. if we don't keep a pointer to the parent, we need approximately O(n). I posted this question to get a solution for O(log n)

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

Here are the steps to calculate next unoccupied leaf (we have a pointer to the parent node):

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

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

This is O(log n), but needs a pointer to the parent.

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

O(n) solution would be pretty easy, just level order the tree and we get the location of the next unoccupied node.

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

My question is: how to locate next unoccupied node in O(log n) without using a parent pointer.

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

Thanks.

谢谢。

回答by Solace

To implement a heap with a binary tree with O(log n) time complexity, you need to store the total number of nodes as an instance variable.

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

Suppose we had a heap of 10 total nodes.

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

If we were to add a node...

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

We increment the total number of nodes by one. Now we have 11 total nodes. We convert the new total number of nodes (11) to its binary representation: 1011.

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

With the binary representation of the total nodes (1011), we get rid of the first digit. Afterwards, we use 011 to navigate through the tree to the next location to insert a node in. 0 means to go left and 1 means to go right. Therefore, with 011, we would go left, go right, and go right...which brings us to the next location to insert in.

用总节点数 (1011) 的二进制表示，我们去掉第一位数字。之后，我们使用 011 在树中导航到下一个要插入节点的位置。0 表示向左走，1 表示向右走。因此，使用 011，我们会向左、向右、然后向右……这会将我们带到下一个要插入的位置。

We examined one node per level, making the time complexity O(log n)

我们每层检查一个节点，使时间复杂度 O(log n)

回答by Puneet Jaiswal

My implementation of heap

我的堆实现

public class Heap <T extends Comparable<T>> {
    private T[] arr;
    private int size;

    public Heap(T[] baseArr) {
        this.arr = baseArr;
        size = arr.length - 1;
    }

    public void minHeapify(int i, int n) {
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        int smallest = i;
        if (l <= n && arr[l].compareTo(arr[smallest]) < 0) {
            smallest = l;
        }
        if (r <= n && arr[r].compareTo(arr[smallest]) < 0) {
            smallest = r;
        }

        if (smallest != i) {
            T temp = arr[i];
            arr[i] = arr[smallest];
            arr[smallest] = temp;
            minHeapify(smallest, n);
        }
    }

    public void buildMinHeap() {
        for (int i = size / 2; i >= 0; i--) {
            minHeapify(i, size);
        }
    }

    public void heapSortAscending() {
        buildMinHeap();
        int n = size;
        for (int i = n; i >= 1; i--) {
            T temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            n--;
            minHeapify(0, n);
        }
    }
}

回答by coderz

The binary tree can be represented by an array:

二叉树可以用数组表示：

import java.util.Arrays;

public class MyHeap {
    private Object[] heap;
    private int capacity;
    private int size;

    public MyHeap() {
        capacity = 8;
        heap = new Object[capacity];
        size = 0;
    }

    private void increaseCapacity() {
        capacity *= 2;
        heap = Arrays.copyOf(heap, capacity);
    }

    public int getSize() {
        return size;
    }

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

    public Object top() {
        return size > 0 ? heap[0] : null;
    }

    @SuppressWarnings("unchecked")
    public Object remove() {
        if (size == 0) {
            return null;
        }
        size--;
        Object res = heap[0];
        Object te = heap[size];
        int curr = 0, son = 1;
        while (son < size) {
            if (son + 1 < size
                    && ((Comparable<Object>) heap[son + 1])
                            .compareTo(heap[son]) < 0) {
                son++;
            }
            if (((Comparable<Object>) te).compareTo(heap[son]) <= 0) {
                break;
            }
            heap[curr] = heap[son];
            curr = son;
            son = 2 * curr + 1;
        }
        heap[curr] = te;
        return res;
    }

    @SuppressWarnings("unchecked")
    public void insert(Object e) {
        if (size == capacity) { // auto scaling
            increaseCapacity();
        }
        int curr = size;
        int parent;
        heap[size] = e;
        size++;
        while (curr > 0) {
            parent = (curr - 1) / 2;
            if (((Comparable<Object>) heap[parent]).compareTo(e) <= 0) {
                break;
            }
            heap[curr] = heap[parent];
            curr = parent;
        }
        heap[curr] = e;
    }
}

Usage:

用法：

    MyHeap heap = new MyHeap(); // it is a min heap
    heap.insert(18);
    heap.insert(26);
    heap.insert(35);
    System.out.println("size is " + heap.getSize() + ", top is " + heap.top());
    heap.insert(36);
    heap.insert(30);
    heap.insert(10);
    while(!heap.isEmpty()) {
        System.out.println(heap.remove());
    }

回答by Harish

import java.util.ArrayList;
import java.util.List;

/**
 * @author Harish R
 */
public class HeapPractise<T extends Comparable<T>> {

    private List<T> heapList;

    public List<T> getHeapList() {
        return heapList;
    }

    public void setHeapList(List<T> heapList) {
        this.heapList = heapList;
    }

    private int heapSize;

    public HeapPractise() {
        this.heapList = new ArrayList<>();
        this.heapSize = heapList.size();
    }

    public void insert(T item) {
        if (heapList.size() == 0) {
            heapList.add(item);
        } else {
            siftUp(item);
        }

    }

    private void siftUp(T item) {
        heapList.add(item);
        heapSize = heapList.size();
        int currentIndex = heapSize - 1;
        while (currentIndex > 0) {
            int parentIndex = (int) Math.floor((currentIndex - 1) / 2);
            T parentItem = heapList.get(parentIndex);
            if (parentItem != null) {
                if (item.compareTo(parentItem) > 0) {
                    heapList.set(parentIndex, item);
                    heapList.set(currentIndex, parentItem);
                    currentIndex = parentIndex;
                    continue;
                }
            }
            break;
        }
    }

    public T delete() {
        if (heapList.size() == 0) {
            return null;
        }
        if (heapList.size() == 1) {
            T item = heapList.get(0);
            heapList.remove(0);
            return item;
        }
        return siftDown();
    }

    private T siftDown() {
        T item = heapList.get(0);
        T lastItem = heapList.get(heapList.size() - 1);
        heapList.remove(heapList.size() - 1);
        heapList.set(0, lastItem);
        heapSize = heapList.size();
        int currentIndex = 0;
        while (currentIndex < heapSize) {
            int leftIndex = (2 * currentIndex) + 1;
            int rightIndex = (2 * currentIndex) + 2;
            T leftItem = null;
            T rightItem = null;
            int currentLargestItemIndex = -1;
            if (leftIndex <= heapSize - 1) {
                leftItem = heapList.get(leftIndex);
            }
            if (rightIndex <= heapSize - 1) {
                rightItem = heapList.get(rightIndex);
            }
            T currentLargestItem = null;
            if (leftItem != null && rightItem != null) {
                if (leftItem.compareTo(rightItem) >= 0) {
                    currentLargestItem = leftItem;
                    currentLargestItemIndex = leftIndex;
                } else {
                    currentLargestItem = rightItem;
                    currentLargestItemIndex = rightIndex;
                }
            } else if (leftItem != null && rightItem == null) {
                currentLargestItem = leftItem;
                currentLargestItemIndex = leftIndex;
            }
            if (currentLargestItem != null) {
                if (lastItem.compareTo(currentLargestItem) >= 0) {
                    break;
                } else {
                    heapList.set(currentLargestItemIndex, lastItem);
                    heapList.set(currentIndex, currentLargestItem);
                    currentIndex = currentLargestItemIndex;
                    continue;
                }
            } else {
                break;
            }
        }
        return item;

    }

    public static void main(String[] args) {
        HeapPractise<Integer> heap = new HeapPractise<>();

        for (int i = 0; i < 32; i++) {
            heap.insert(i);
        }
        System.out.println(heap.getHeapList());
        List<Node<Integer>> nodeArray = new ArrayList<>(heap.getHeapList()
                .size());
        for (int i = 0; i < heap.getHeapList().size(); i++) {
            Integer heapElement = heap.getHeapList().get(i);
            Node<Integer> node = new Node<Integer>(heapElement);
            nodeArray.add(node);
        }
        for (int i = 0; i < nodeArray.size(); i++) {
            int leftNodeIndex = (2 * i) + 1;
            int rightNodeIndex = (2 * i) + 2;
            Node<Integer> node = nodeArray.get(i);
            if (leftNodeIndex <= heap.getHeapList().size() - 1) {
                Node<Integer> leftNode = nodeArray.get(leftNodeIndex);
                node.left = leftNode;
            }
            if (rightNodeIndex <= heap.getHeapList().size() - 1) {
                Node<Integer> rightNode = nodeArray.get(rightNodeIndex);
                node.right = rightNode;
            }
        }
        BTreePrinter.printNode(nodeArray.get(0));
        System.out.println(heap.delete());
        nodeArray = new ArrayList<>(heap.getHeapList().size());
        for (int i = 0; i < heap.getHeapList().size(); i++) {
            Integer heapElement = heap.getHeapList().get(i);
            Node<Integer> node = new Node<Integer>(heapElement);
            nodeArray.add(node);
        }
        for (int i = 0; i < nodeArray.size(); i++) {
            int leftNodeIndex = (2 * i) + 1;
            int rightNodeIndex = (2 * i) + 2;
            Node<Integer> node = nodeArray.get(i);
            if (leftNodeIndex <= heap.getHeapList().size() - 1) {
                Node<Integer> leftNode = nodeArray.get(leftNodeIndex);
                node.left = leftNode;
            }
            if (rightNodeIndex <= heap.getHeapList().size() - 1) {
                Node<Integer> rightNode = nodeArray.get(rightNodeIndex);
                node.right = rightNode;
            }
        }
        BTreePrinter.printNode(nodeArray.get(0));
    }
}

public class Node<T extends Comparable<?>> {
    Node<T> left, right;
    T data;

    public Node(T data) {
        this.data = data;
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class BTreePrinter {

    public static <T extends Comparable<?>> void printNode(Node<T> root) {
        int maxLevel = BTreePrinter.maxLevel(root);

        printNodeInternal(Collections.singletonList(root), 1, maxLevel);
    }

    private static <T extends Comparable<?>> void printNodeInternal(
            List<Node<T>> nodes, int level, int maxLevel) {
        if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
            return;

        int floor = maxLevel - level;
        int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
        int firstSpaces = (int) Math.pow(2, (floor)) - 1;
        int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

        BTreePrinter.printWhitespaces(firstSpaces);

        List<Node<T>> newNodes = new ArrayList<Node<T>>();
        for (Node<T> node : nodes) {
            if (node != null) {
                String nodeData = String.valueOf(node.data);
                if (nodeData != null) {
                    if (nodeData.length() == 1) {
                        nodeData = "0" + nodeData;
                    }
                }
                System.out.print(nodeData);
                newNodes.add(node.left);
                newNodes.add(node.right);
            } else {
                newNodes.add(null);
                newNodes.add(null);
                System.out.print("  ");
            }

            BTreePrinter.printWhitespaces(betweenSpaces);
        }
        System.out.println("");

        for (int i = 1; i <= endgeLines; i++) {
            for (int j = 0; j < nodes.size(); j++) {
                BTreePrinter.printWhitespaces(firstSpaces - i);
                if (nodes.get(j) == null) {
                    BTreePrinter.printWhitespaces(endgeLines + endgeLines + i
                            + 1);
                    continue;
                }

                if (nodes.get(j).left != null)
                    System.out.print("//");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(i + i - 1);

                if (nodes.get(j).right != null)
                    System.out.print("\\");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
            }

            System.out.println("");
        }

        printNodeInternal(newNodes, level + 1, maxLevel);
    }

    private static void printWhitespaces(int count) {
        for (int i = 0; i < 2 * count; i++)
            System.out.print(" ");
    }

    private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
        if (node == null)
            return 0;

        return Math.max(BTreePrinter.maxLevel(node.left),
                BTreePrinter.maxLevel(node.right)) + 1;
    }

    private static <T> boolean isAllElementsNull(List<T> list) {
        for (Object object : list) {
            if (object != null)
                return false;
        }

        return true;
    }

}

Please note that BTreePrinter is a code I took somewhere in Stackoverflow long back and I modified to use with 2 digit numbers.It will be broken if we move to 3 digit numbers and it is only for simple understanding of how the Heap structure looks.A fix for 3 digit numbers is to keep everything as multiple of 3. Also due credits to Sesh Venugopal for wonderful tutorial on Youtube on Heap data structure

请注意，BTreePrinter 是我很久以前在 Stackoverflow 某处使用的代码，我修改为使用 2 位数字。如果我们移动到 3 位数字，它将被破坏，它仅用于简单理解堆结构的外观。A修复 3 位数字是将所有内容保留为 3 的倍数。还要感谢 Sesh Venugopal 在 Youtube on Heap 数据结构上的精彩教程