Removing the highest-priority task from a heap leaves a gap at the root. Filling it with the array’s last element preserves the heap’s shape, but the replacement may have lower priority than a child. Pushdown restores priority order by moving that element toward the leaves. section 2.6.4
To push an element down in an array-backed heap:
- Start at the affected index, usually the root after a top operation. If the node is a leaf, stop. section 2.6.2 section 2.6.4
- Find its highest-priority child. If that child has higher priority, exchange them and continue from the child’s index. section 2.6.2
- Stop when no child has higher priority. The element has found a position that does not violate heap priority order. section 2.6.2
This is the downward counterpart of bubble up: bubble up checks an altered node against its parent, while pushdown checks it against its children. A decrease in a node’s priority can also call for pushdown. section 2.6.2
Listing 2.5 Optimizing the pushDown method
function pushDown(pairs, index=0)
current ← pairs[index] #1
while index < firstLeafIndex(pairs) do #2
(child, childIndex) ← highestPriorityChild(index) #3
if child.priority > current.priority then #4
pairs[index] ← pairs[childIndex] #5
index ← childIndex
else #6
break
pairs[index] ← current #7
The optimized pseudocode holds the displaced element aside, moves higher-priority children upward, and writes the element once at its final position instead of swapping at every level. section 2.6.2
For a heap with n elements and at most D children per node, pushdown takes O(D × log_D(n)) time in the worst case: it can descend through the heap while comparing children at each level. A larger branching factor shortens the path but makes child selection costlier. Measurements of top and its pushdown helper show a local running-time minimum around D = 9 for the tested workload, not a universal best choice. section 2.6.2 section 2.10.2
Treap deletion uses a related downward move with a different stopping rule. It repeatedly rotates the highest-priority child above the node being deleted until that node becomes a leaf, then disconnects it. Unlike heap repair, it need not stop when priorities are in order: deletion requires reaching a leaf. section 3.3.5
