Binary heap: Difference between revisions

Revision as of 14:33, 15 October 2004

Revision as of 02:44, 5 November 2004

Line 74:

== Heap implementation ==

It is perfectly possible to use a traditional binary tree data structure to implement a binary heap. There is an issue with finding the adjacent element on the last level on the binary heap when adding an element which can be resolved algorithmically or by adding extra data to the nodes, called "threading" the tree -— that is, instead of merely storing references to the children, we store the [[inorder]] successor of the node as well.

However, using a tree data structure requires the storage of references to the other nodes in the heap. Using an array, with restrictions on the indices that elements are stored at, it is also possible to use this array to implement a heap.

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

WeHowever, constructa themore heapcommon byapproach imaginingis thatto elementsstore the heap in thean array. Any binary tree ''a''can arebe placedstored in thean array, asbut follows: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 rightin the figure.

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