next up previous contents
Next: The siftdown procedure Up: The MinMax Heap. A Previous: The MinMax Heap. A

The siftup procedure

The siftup operation is very similar to the the siftup of the basic heap. The main difference being that two versions must exist. One to do a siftup from a max level and one to do a siftup from a min level. The only difference between the two versions is that the ordering relation is reversed.

  program101

The correctness of one detail in this program requires extra consideration. When the element c is swapped with its grandparent, the parent(c) is not involved at all. The correctness rests on the fact that since grandparent(c) is on a maxlevel we can be sure that parent(c) is less than grandparent(c), and consequently the heap property remains true when element grandparent(c) is moved to position c.



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