Binary heap: Difference between revisions

Revision as of 03:02, 12 December 2003

Revision as of 08:33, 10 March 2004

Line 1:

[[de:Binärer Heap]][[pl:Kopiec (informatyka)]]

'''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''+1 and 2''n''+12; so item 10's children are items 21 and 32, 21's children are items 43 and 54, 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.

Line 17:

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 2''n''+1 and 2''n''+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|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 [[Big O notation|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.