next up previous contents
Next: A note on terminology Up: Implicit Heaps Previous: Insert element.- The siftup

Delete max element.- The siftdown procedure

Deletion of the maximum element from the heap must find an element to replace the maximum element (in the root). As for insertion this is done in to steps. First the maximum element (the root) is replaced with the last element of the heap, and next the new root is shifted down the tree along the path of the largest children. In C the siftdown operation can be described like this

  program49

It should be noted that the loop condition of siftdown is selected so that all the special conditions encountered at the bottom of the tree are handled outside the loop. The price that must be payed for this efficiency is that some of the inner loop code must be repeated in a slightly different form outside the loop. This idea is used to improve performance of the different implementations of the siftdown operations throughout heaplab.

The performance of the siftdown operation is especially critical for the heapsort algorithm. The worst case running time for a siftdown operation is tex2html_wrap_inline1231 .



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