Binary heap

Values stored in a binary min-heap

Binary heap is a complete binary tree, in which every parent node has a higher (or equal) priority than both of its descendants. If the deepest level of the tree is not fully filled, the nodes are stored in left to right manner.

An important property of an array based implementation of the binary heap is that if the parent is stored at index and the array is indexed starting at 1, than the descendants of the parent are placed at indexes and 2n+1 . This property is guaranteed by the fact that the heap does not contain any empty spaces.

The property of being a heap is recursive – every subtree of a heap is also a heap. Thanks to this feature the heap behaves as a priority queue, because the element of the highest priority must be always present at the top of the heap (this can be used for sorting an array – heapsort algorithm).

If the higher value is considered as a higher priority than the heap is called max-heap, on the contrary the min-heap is a heap in which the lower value is considered as a higher priority.

Operations

Repair top

Let's suppose we have a binary heap and we know that the top of the heap is misplaced. The helper repairTop procedure relocates this node to the correct position. The implementation is simple – in every step the procedure compares the parent with of of its descendants, if one of them has a higher priority, than the procedure swaps the nodes. If both descendants have higher priority, than the procedure swaps the parent with the child with higher priority. Now the procedure iteratively repeats the process at he next level until it reaches the deepest level of the heap or the parent has a higher priority than both of his children.

The asymptotic complexity of the repairTop procedure is $O(\\log_{2}{n})$ because the heap has a logarithmic depth.

Heapify

The helper procedure heapify builds heap in a given array. Because the being a heap property is recursive, the procedure has to repair tops of all non-trivial subheap (indexes $n/2 \\rightarrow 1$ ). After the termination of the repairing loop the given array represents a binary heap. Asymptotic complexity of the heapify procedure is O(n) .

Insert

The insert operation works in an opposite way than repairTop. The new element is added at the end of the heap and it ascends through the heap while it has a higher priority than its parent. Asymptotic complexity of the inserion is $O(\\log_{2}{n})$ .

Top

The operation top returns the element of the heap with the highest priority. Because it just returns the first element of the array, the asymptotic complexity of this operation is constant – O(1) .

Return top

The return top operation retrieves and deletes the element of the heap with the highest priority. In fact it swaps the top element with the last one, shorthens the heap (decrements its size variable) and repairs the top of the heap. The asymptotic complexity of this approach is equal to the complexity of the repairTop operation – $O(\\log_{2}{n})$ .

Merge

The merge operation merges two heaps into one – it creates one array and copies all elements of both heaps into it. Than the algorithm heapifies the array. The asymptotic complexity of the merge operation is O(m+n) , where is the size of the first array and is the size of the second array.

Code

Java

/**
 * Binary heap (min-heap)
 * @author Pavel Micka
 */
public class BinaryHeap {

    private int[] array;
    private int size; // size of the array (keep in mind that we are indexing from 1)

    /**
     * Constructor
     * @param arraySize maximal size of the heap
     */
    public BinaryHeap(int arraySize) {
        this.array = new int[arraySize + 1]; // first index will be always empty
        this.size = 0;
    }

    /**
     * Konstruktor
     * @param arraySize velikost haldy
     */
    public BinaryHeap(int[] source) {
        this.array = new int[source.length + 1]; // first index will be always empty
        System.arraycopy(source, 0, array, 1, source.length);
        this.size = 0;
    }

    /**
     * Perform merging of the heaps
     * @param heap heap to be merged with this heap
     */
    public void merge(BinaryHeap heap) {
        int[] newArray = new int[this.size + heap.size + 1];

        System.arraycopy(array, 1, newArray, 1, this.size);
        System.arraycopy(heap.array, 1, newArray, this.size + 1, heap.size);

        size = this.size + heap.size;
        array = newArray;
        heapify(newArray);
    }

    /**
     * Return array of all elements in this heap
     * @return array of all elements in this heap
     */
    public int[] getAll() {
        return Arrays.copyOfRange(array, 1, this.size + 1);
    }

    /**
     * Insert the array to the heap
     * @param i element to be inserted
     */
    public void insert(int i) {
        size++;
        int index = this.size;
        while (i < array[index / 2] && index != 0) { 
            array[index] = array[index / 2];
            index /= 2; 
        }
        array[index] = i; 
    }

    public int top() {
        if (getSize() == 0) {
            throw new IllegalStateException("The heap is empty");
        }
        return array[1];
    }

    /**
     * Remove and retrive the top of the heap
     * @return element with the highest priority
     */
    public int returnTop() {
        if (getSize() == 0) {
            throw new IllegalStateException("The heap is empty");
        }
        int tmp = array[1];
        array[1] = array[this.size];
        size--;
        repairTop(this.size, 1);
        return tmp;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 1; i <= this.size; i++) {
            builder.append(array[i]).append(" ");
        }
        return builder.toString();
    }

    /**
     * @return the size
     */
    public int getSize() {
        return size;
    }
    
    /**
     * Create the heap using the given array
     * @param array array
     */
    private void heapify(int[] array) {
        for (int i = array.length / 2; i > 0; i--) {
            repairTop(this.size, i);
        }
    }
    
    /**
     * Place the top of the heap to the correct position in the heap
     * @param bottom last index of the array which can be touched
     * @param topIndex index of the top of the heap
     */
    private void repairTop(int bottom, int topIndex) {
        int tmp = array[topIndex];
        int succ = topIndex * 2;
        if (succ < bottom && array[succ] > array[succ + 1]) {
            succ++;
        }

        while (succ <= bottom && tmp > array[succ]) {
            array[topIndex] = array[succ];
            topIndex = succ;
            succ = succ * 2;
            if (succ < bottom && array[succ] > array[succ + 1]) {
                succ++;
            }
        }
        array[topIndex] = tmp;
    }    
}