Binary heap

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

The diagram on the left is somewhat deceptive in that heaps are conventionally in decreasing order rather than increasing order because of their use as priority queues. The diagram on the right is a more traditional heap.

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

Flattening these two heaps into a traditional zero based array will produce the following arrays:

 index: 0  1  2  3  4  5  6  7  8  9 10
 left:  1  2  3  4  5  6  7  8  9 10 11
 right: 11 9 10  5  6  7  8  1  2  3  4

Notice in this case, it changes the formulas for the child indices to be 2n+1 and 2n+2. The fact that a heap can easily be flattened is the 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.

If you regard the array as a screwed-up heap, you can fix it in O(n) time by restoring the heap property from the bottom up. Consider each trio containing a node and its two children, starting from the end of the array; if the greatest value of the three nodes is not in the top node, exchange it with the top node. This puts the former top node at the top of a subtree which may contain nodes greater than it is; so we must compare it with its new children and possibly repeat the process.

External links

• http://mathworld.wolfram.com/Heap