4 Heaps
A heap are a datastructure for the efficient storage and retrieval of elements
equipped with an order, where only access to the maximal element
is required. To this end, the elements need not be ordered linearly in a
list; instead the concrete representation of a heap is a (binary) tree. To
give easy access to the maximal element, the tree additionally satisfies the
``heap property'', requiring that the key of a node is greater or equal the
value of its children (it there are any).
So, heaps respect the order of its elements, but is much more liberal than
binary search trees. This makes is much easier (and less important) to keep
the heaps balanced. In addition to the basic ordering requirement, one can
distinguish heap representations according to which amount the trees are
balanced or not. Since the heap's ordering condition is much more liberal than
for search tree, it is easy to keep a heap balanced, since if the tree is
about to ge imbalanced (by adding a new element or removing one) one can
always swap the left and the right subtree without violating the
heap-condition to make it balanced again. Since maintaining the balance is
cheap, the choice of the balance condition is determined by the access
functions to the heap.
The module Heap implementes two sorts of heaps. As abstract datatypes they
differ on on whether they support merging to heaps or not. The corresponding
interfaces are called HEAP and MHEAP (for
mergeable heap).
The standard heaps are implemented as binary trees. All operations
manipulating the tree maintain (besides the heap-condition, of course) the
balancing condition: the right subtree of a node has the equal number of nodes
or one less. This condition is slightly less strict than the one in
[CLR90], which uses arrays as representation
and which requires that a the ``bottom row'' of the tree the nodes are filled
from left to right.
The balancing condition is maintained in a very simple way, namely by
inserting a new element each time at the left subtree but, at the same time,
switching left and right son. This obvioulsy maintains the tree balanced in
the way desrcibed above. When deleting a leaf, the reverse is done.
The mergeable heaps of interface HEAP support merging.
The trees satisfy a different balancing condition, requiring that the depth of
the left subtree is always larger or equal than the depth of the right
subtree. Heaps satisfying this property are called leftist heaps.
The merge-operating here is the fundamental one, the other operations, at
least the non-trivial ones, are based on merging. This means the effictiency
of the implementation crucially hinges in the efficiency of merging.
In general, two heaps can be merged by choosing in each heap a path from the
root to a leaf and merging the heaps along the two paths and the shorter the
two paths, the faster the merging. Leftists heaps now have the nice property
that one can find the shortest path at a standard place: always the overall
shortest path from the root to a leaf is the rightmost one.
Pages last (re-)generated October 28, 2002 (Martin Steffen)