Content deleted Content added
Added traditional heap diagram, more explanation, and a few related links |
Corrected my diagram and text |
||
Line 1:
'''Binary heaps''' are a particular kind of [[heap]] that only has two children. Binary heaps are commonly represented by [[array]]s 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 2''n'' and 2''n''+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 queue]]s. The diagram on the right is a more traditional heap
1
/ \ / \
/ \ / \
2 3
/ \ / \ / \ / \
4 5 6 7
/ \ / \ / \ / \
8 9 10 11 1
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:
Notice in this case, it changes the formulas for the child indices to be 2''n''+1 and 2''n''+2. The fact that a heap can easily be flattened is the basis for the [[heapsort]] algorithm.
If you regard the array as a screwed-up heap, you can fix it in [[Big O|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.
| |||