Implement Heap using a Binary Tree

Question

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

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)?

Thanks Shekhar

Answer 1

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.

Suppose we had a heap of 10 total nodes.

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.

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.

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

Answer 2

You won't implement the heap IN binary tree, because the heap is A binary 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:

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

Here is my Heap.java file:

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.

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:

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.

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