Binary heap

Binary heaps are a particular kind of heap data structure such that each node only has two children, and the heap property is placed upon elements in the heap, such that internal nodes contain data that is either larger or smaller than elements in its children.

Min-heaps and max-heaps

Heaps can be organized so that the largest element in the heap is at the root of the tree always, or that the smallest element of the heap is at the root. These heaps are termed max-heaps and min-heaps respectively. Conventionally, max-heaps are used, since they are readily applicable for use in priority queues.

        1               11
      /   \           /    \
     2     3         9     10
    / \   / \       / \    / \
   4   5  6  7     5   6  7   8
  / \ / \         / \ / \
 8  9 10 11      1  2 3  4

Binary heaps are also commonly represented by arrays of values. For example, the root of the tree could be item 0 in the array, and the children of item n are the items at 2n+1 and 2n+2; so item 0's children are items 1 and 2, 1's children are items 3 and 4, etc. This allows you to regard any 1-based array as a possibly-screwed-up heap.

The fact that we retrieving the maximum/minimum element from a heap is basis for the heapsort algorithm. Also note that the ordering of siblings in a heap is not specified by the heap property, so the two children of a parent can be interchanged.

Heap operations

Adding to the heap

If we have a heap, and we add an element, we can perform an operation known as up-heap, bubble-up, or sift-up in order to restore the heap property. We can do this in O(log n) time, using a binary heap, by adding the element on the bottom level of the heap regardless, then considering the added element and it's parent and swapping the element and its parent if need be until we are assured the heap property remains. We do this at maximum for each level in the tree - the height of the tree, which is O(log n).

Say we have a max-heap

and we want to add the number 15 to the heap. We first place the 15 in the position marked by the X. However the heap property is violated since 15 is greater than 8, so we need to swap the 15 and the 8. So, we have the heap looking as follows after the first swap:

However the heap property is still violated since 15 is greater than 11, so we need to swap again:

which is a valid max-heap.

Deleting the root from the heap

The procedure for deleting the root from the heap - effectively giving the maximum element in a max-heap or the minimum element in a min-heap - is similar to up-heap. What we do is remove the root, then replace it with the last element on the last level. So, if we have the same max-heap as before,

we remove the 11 and replace it with the 4.

Now the heap property is violated since 8 is greater than 4. If we swap these two elements, we have restored the heap property and we need not swap elements further:

Heap implementation

It is perfectly possible to use a traditional tree data structure to implement a binary heap. There is an issue with finding the adjacent element on the last level on the binary heap when adding which can be resolved algorithmically or by adding extra data to the nodes, "threading" the tree - that is, instead of merely storing references to the children, the inorder successor of the node as well.

However, using a tree data structure requires the storage of references to the other nodes in the heap. Using an array, with restrictions on the indices that elements are stored at, it is also possible to use this array to implement a heap.

A small complete binary tree stored in an array

We construct the heap by imagining that elements in the tree a are placed in the array as follows: for each index i, element a[i] is the parent of two children a[2i+1] and a[2i+2], as shown right.

The upheap/downheap operations can be stated then in terms of an array as follows: suppose that the heap property holds for the indices b, b+1, ..., e. The sift-down function extends the heap property to b-1, b, b+1, ..., e. Only index i = b-1 can violate the heap property. Let j be the index of the largest child of a[i] within the range b, ..., e. (If no such index exists because 2i > e then the heap property holds for the newly extended range and nothing needs to be done.) By swapping the values a[i] and a[j] the heap property for position i is established. The only problem now is that the heap property might not hold for index j. The sift-down function is applied tail-recursively to index j until the heap property is established for all elements.

The sift-down function is fast. In each step it only needs two comparisons and one swap. The index value where it is working doubles in each iteration, so that at most log₂ e steps are required.