next up previous contents
Next: Insert element.- The siftup Up: Heaps - A Priority Previous: The Heap data structure

Implicit Heaps

  A particularly simple and beautiful implementation of the heap structure is the implicit heap. Data is simply put into an array tex2html_wrap_inline1217 and the childrens of element x[i] are defined to be the elements x[2i] and x[2i+1]. Thus the parent of the element c can be found at c/2 (integer division).

With this structure the heap uses absolutely no space beyond what is needed to store the elements, and the shape property is guaranteed to hold.





Jesper Bojesen
Sat Apr 3 18:07:59 METDST 1999