Bubble up restores a heap after an inserted or updated element violates parent ordering. In a max-heap, a higher-priority child moves toward the root until its parent has equal or greater priority. section 2.6.1 section 2.6.3
Implement the procedure by repeatedly comparing the element with its parent:
- Start at the element's array index, commonly the newly appended final position. section 2.6.1 section 2.6.3
- Compute the parent index and compare priorities. section 2.6.1
- Swap when the current element has higher priority; otherwise stop because the heap ordering is restored. section 2.6.1
- Repeat until the element reaches the root or no longer outranks its parent. section 2.6.1
Priority 9 moves above priority 8
In a ternary max-heap, the element at index 7 has priority 9 while its parent at index 2 has priority 8. Swap them, then compare the moved element with its new parent at index 0, whose priority 10 stops further bubbling. section 2.6.1
Listing 2.3 An optimization of the bubbleUp method
function bubbleUp(pairs, index=|pairs|-1) #1
current ← pairs[index] #2
while index > 0 do #3
parentIndex ← getParentIndex(index) #4
if pairs[parentIndex].priority < current.priority then #5
pairs[index] ← pairs[parentIndex] #6
index ← parentIndex #7
else #8
break
pairs[index] ← current #9
Use the optimized pseudocode to see how one saved element moves upward while parent entries shift downward, reducing assignments. section 2.6.1
