next up previous contents
Next: Comparison of the Min-Max Up: The MinMax Heap. A Previous: The siftup procedure

The siftdown procedure

As for the siftup, there must be two versions of the siftdown operation. One for use on max-levels and one for use on min-levels.

(I believe that it is possible to use C++ templates to avoid this replication of code. It has not been implemented, but anyone interested in a small exercise in C++ programming should give it a try.)

  program115

A few comments are needed to explain this code.

The maxgrandchild function returns, as the name suggests, an index to the largest grandchild. Since the requirement of the heap property is that element p must be larger than both all children and all grandchildren, it is tempting to conclude that the program is incorrect. Anyway,- the same heap property guarantes that any grandchild of p is larger than its parent, and since the loop condition ensures that all grandchildrens do exist, we do not have to check the childrens of p.



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