Binary heap: Difference between revisions

Revision as of 13:21, 20 June 2004

Revision as of 07:29, 27 June 2004

Line 1:

[[Category:Trees (structure)]]

'''Binary heaps''' are a particular kind of [[heap]] [[data structure]] such that each node only has two children., Binary heaps are commonly represented by [[array]]s of values. For example,and the rootheap ofproperty theis treeplaced couldupon be item 0elements in the arrayheap, andsuch thethat children[[internal ofnodes]] itemcontain ''n''data arethat theis itemseither atlarger 2''n''+1or andsmaller 2''n''+2;than soelements itemin 0'sits 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.

== Min-heaps and max-heaps ==

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.

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 queue]]s.

1 11

Line 12 ⟶ 13:

8 9 10 11 1 2 3 4

Binary heaps are also commonly represented by [[array]]s 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 2''n''+1 and 2''n''+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.

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

The fact that awe heapretrieving canthe easilymaximum/minimum beelement flattenedfrom isa theheap is 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.

== Heap maintenance ==

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.

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 [[Big O notation|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'').

==External links==