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
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 
.
