Binary heap: Difference between revisions

Revision as of 02:44, 5 November 2004

Revision as of 02:49, 5 November 2004

Line 1:

[[Category:Trees (structure)]]

'''Binary heaps''' are a particularparticularly simple kind of [[heap]] [[data structure]] suchcreated thatusing eacha node[[binary onlytree]]. hasIt twocan children,be andseen theas heapa propertybinary istree placedwith uponthe elementsadditional inconstraint thethat heap,each suchnode thatis [[internallarger nodes]]than containall dataits thatchildren is(for eithera largermax-heap) or smaller than elements inall its children. (for a min-heap).

== Min-heaps and max-heaps ==

Line 13:

8 9 10 11 1 2 3 4

Retrieving the maximum/minimum element from a heap is the basis for the [[heapsort]] algorithm. Also noteNote 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 freely interchanged.

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 [[binary tree]] and hence, a heap.

Retrieving the maximum/minimum element from a heap 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.

== Heap operations ==

Line 77 ⟶ 75:

[[Image:Binary_tree_in_array.png|right|A small complete binary tree stored in an array]]

However, a more common approach is to store the heap in an array. Any binary tree can be stored in an array, but because a heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, for each index ''i'', element ''a''[''i''] is the parent of two children ''a''[2''i''+1] and ''a''[2''i''+2], as shown in the figure. This approach is particularly useful in the [[heapsort]] algorithm, where it allows the space in the input array to be reused to store the heap.

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''.