Binary heap: Difference between revisions

Revision as of 19:38, 16 July 2004

Revision as of 19:29, 11 August 2004

Line 74:

== Heap implementation ==

It is perfectly possible to use a traditional 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 which can be resolved algorithmically or by adding extra data to the nodes, "threading" the tree - that is, instead of merely storing references to the children, the [[inorder successor]] 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.