Content deleted Content added
m update and shove some stuff here from Heapsort |
last maj |
||
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]] 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.
| |||