In order to control the the depth of the heap, the amount of empty space in each node must be bounded. This is done by deciding that when the load factor of a node drops below some suitable value (e.g. 0.5), the node is refilled completely with the largest elements of its childrens. If in turn, the load of any of the childrens drops below the threshold value, the process is repeated for each of these. If the load factor of a leaf node drops below the threshold, it is refilled with elements from the last node of the heap, and the elements of the node is then sifted up towards the root. The siftup is best done so that the load factors of the nodes affected do not change. In this way we avoid starting yet another series of refills.
At first sight this approach seems disastrous.- Extracting one single element from the heap may cause every node in the heap to be touched. Anyway, the result in [6] shows that when the cost is amortized over a sequence of heap operations, it is much more reasonable.
It is interesting and illustrative to observe that in the special case where the node size is assumed to be a single element, this idea is equivalent to an old fashioned trick for improving the performance of the siftdown operation in the traditional heap.
When the top element is removed, the load factor of the top node drops to 0,- effectively turning it into a hole.- This hole is sifted all down to the bottom of the heap, where it is filled with the last element of the heap, and thereafter this element is sifted upwards. Because the element was taken from the bottom of the heap, it is small and does not move very far up. In the case of the traditional heap, the saving of this approach is from the fact that sifting a hole only takes half as many comparisons (in a binary heap) as sifting an element.