next up previous contents
Next: Implicit Heaps Up: Heaps - A Priority Previous: Heaps - A Priority

The Heap data structure

The heap data structure is an ordinary binary tree with two properties. The shape property and the heap property.

The shape property states that the tree is perfectly balanced and that the elements at the bottom level are pushed as far to the left as possible. This property is best described graphicaly.

tex2html_wrap1215

As this figure suggests, the tree has no holes and there is leaf elements on at most two levels of the tree.

The heap property simply states that every element of the tree is larger than any of its descendants if they exists. In particularly the largest element of the heap is the root element. Of course the opposite ordering also defines a heap. Depending on the ordering, a heap is called a max-heap or a min-heap respectively.



Jesper Bojesen
Wed Nov 4 15:35:15 MET 1998