Binary Heap

Among different kinds of tree-like data structures there is one quite specific and very useful.

Imagine the binary tree of the following kind:

                    3
                    |
             5------+------7
             |             |
         9---+---6     8---+---12
         |       |     |        |
      14-+-11 10-+-   -+-      -+-

It has two important properties:

1. Value of each node is smaller than values of its children (the "heap property")
2. Tree is filled so that only, perhaps, rightmost leafs of the lowest level (row) are empty

Such a tree is called a Binary Heap and is famous because:

• it is easy to fetch smallest element from it (which is always in the root) and rebuild the heap in log2(N) swaps of elements, i.e. quite efficiently;
• insertion of new element to the end also requires rebuild of no more than log2(N) swaps;
• the whole structure could be placed into simple array instead of building tree with dynamically allocated objects.

This allows to use such structure in the popular HeapSort algorithm which is the rival to QuickSort because its efficiency does not degrade in "the worst case" and because sorting is done "in-place" (even no log(N) space at stack is needed).

Another popular usage is the efficient implementation of Priority Queue very important structure, so it exists out-of-the box among Java standard classes under the name PriorityQueue.

Let us see how the Binary Heap is working.

Binary Heap Implementation

We shall store the heap in the array, so that if it contains N elements, all cells from 0 to N - 1 are filled (i.e. array is always filled from the beginning). Initially the array is empty (N is 0).

For each element with index K its parent has index floor((K - 1) / 2) where "floor" means rounding down, to the nearest smaller integer. Also for element with index K its children have indices 2 * K + 1 and 2 * K + 2, though of course they may not exist if N is smaller than these values.

So for root element with index 0 its children have indices 1 and 2 - and, for example, for element with index 3 its parent is at index 1 while its children have indices 7 and 8 (if the heap contains at least 8 or 9 elements respectively).

Insertion of a new element

We place an element to the current end (i.e. put to the N-th cell and then increase N). This can violate the "heap property", so we compare the newly inserted element with its parent. Swap them if the parent is greater.

Then do the same for parent - compare it with its parent (i.e. grandparent) and swap if necessary. Continue until swaps would not stop (meaning that heap property is restored) or until root is reached (root have no parent and there is nothing to swap more).

As an exercise, prove yourself that the "heap property" is preserved with such an algorithm.

Deletion of the minimum element

When extracting from the heap, we usually take only the topmost, i.e. minimal element. We simply fetch it from the root.

Since the root becomes empty, we take the last element and move its value to the root. For this we decrement N and then move N-th element to 0-th cell.

Obviously after this the "heap property" could be broken between the root and its children. We need to fix it with a series of swaps, going from root downwards.

For this we compare the root with its children and swap with the child for which the "heap property" is violated. If it is the case with both children, then we swap with the smallest of them (Can you explain why?)

Then we should again check the heap property at the place where the element from the root was moved and so proceed until swaps stop or until we came to elements with no children.

Checking for two children and checking for their existence could look hard at first. However the following sequence of actions is simple enough:

• let cur be the index of currently checked element, initially it is 0;
• let the p be the temporary index or pointer, initially pointing to current element too;
• if cur element have left child and the child's value is less than p-th - then let p point to left child;
• if cur element have right child and the child's value is less than p-th - then let p point to right child;
• if p now does not point to cur then swap these elements and assign p to cur, proceeding from the 2-nd step;
• otherwise stop.

Refer to Binary Heap article of wikipedia for more verbose explanations.

Other operations

Some algorithms may require extending Binary Heap with additional operations, most important of them are:

• being able to find the position of the given value in a heap without traversing the whole heap - usually done with the help of additional data structure, like HashTable;
• being able to delete arbitrary element from the heap, rebuilding no more than log2(N) nodes;
• build the heap from array in O(N) operations.

As for now you only need to be aware that such operations are really possible and you can always find more explanations in internet.

If you want to have practice, see our Binary Heap problem.