Tracing Remove Operations
Let's trace complete removal sequences to understand how bubble-down restores the heap property.
Example 1: Complete Removal Sequence
Starting heap:
[90]
/ \
/ \
[75] [80]
/ \ / \
/ \ / \
[50] [60] [70] [40]
Array: [90, 75, 80, 50, 60, 70, 40]
Index: 0 1 2 3 4 5 6
Size: 7
Remove #1: Remove 90
Step 1: Save 90 (to return)
Step 2: Replace root with last element (40)
Step 3: Decrease size to 6
[40]
/ \
/ \
[75] [80]
/ \ /
/ \ /
[50] [60] [70]
Array: [40, 75, 80, 50, 60, 70]
0 1 2 3 4 5
Bubble-down from index 0:
─────────────────────────
Compare children: 75 vs 80 → 80 is larger
Compare parent with larger child: 40 < 80
Action: Swap 40 with 80
After first swap:
[80]
/ \
/ \
[75] [40]
/ \ /
/ \ /
[50] [60] [70]
Array: [80, 75, 40, 50, 60, 70]
0 1 2 3 4 5
Continue from index 2:
────────────────────────
Only left child (70) exists
Compare: 40 < 70
Action: Swap 40 with 70
After second swap:
[80]
/ \
/ \
[75] [70]
/ \ /
/ \ /
[50] [60] [40]
Array: [80, 75, 70, 50, 60, 40]
0 1 2 3 4 5
Continue from index 5:
────────────────────────
No children (leaf node) → Stop
Final heap:
[80]
/ \
/ \
[75] [70]
/ \ /
/ \ /
[50] [60] [40]
Return: 90
Total swaps: 2
Remove #2: Remove 80
Starting:
[80]
/ \
/ \
[75] [70]
/ \ /
/ \ /
[50] [60] [40]
Array: [80, 75, 70, 50, 60, 40]
0 1 2 3 4 5
Step 1: Save 80
Step 2: Replace root with last element (40)
Step 3: Decrease size to 5
[40]
/ \
/ \
[75] [70]
/ \
/ \
[50] [60]
Array: [40, 75, 70, 50, 60]
0 1 2 3 4
Bubble-down from index 0:
─────────────────────────
Compare children: 75 vs 70 → 75 is larger
Compare: 40 < 75
Action: Swap 40 with 75
After first swap:
[75]
/ \
/ \
[40] [70]
/ \
/ \
[50] [60]
Array: [75, 40, 70, 50, 60]
0 1 2 3 4
Continue from index 1:
────────────────────────
Compare children: 50 vs 60 → 60 is larger
Compare: 40 < 60
Action: Swap 40 with 60
After second swap:
[75]
/ \
/ \
[60] [70]
/ \
/ \
[50] [40]
Array: [75, 60, 70, 50, 40]
0 1 2 3 4
Continue from index 4:
────────────────────────
No children (leaf) → Stop
Return: 80
Total swaps: 2
Remove #3: Remove 75
Starting:
[75]
/ \
/ \
[60] [70]
/ \
/ \
[50] [40]
Array: [75, 60, 70, 50, 40]
0 1 2 3 4
After swapping with last (40) and decreasing size:
[40]
/ \
/ \
[60] [70]
/
/
[50]
Array: [40, 60, 70, 50]
0 1 2 3
Bubble-down:
────────────
Compare children: 60 vs 70 → 70 is larger
Compare: 40 < 70
Swap: 40 with 70
After swap:
[70]
/ \
/ \
[60] [40]
/
/
[50]
Array: [70, 60, 40, 50]
0 1 2 3
Continue from index 2:
────────────────────────
Left child would be at 2*2+1 = 5
5 >= 4 (size) → No children!
Stop
Return: 75
Total swaps: 1
Continuing: Remove 70, then 60, then 50, then 40...
Sequence of returned values:
90, 80, 75, 70, 60, 50, 40
Notice: This is **descending order**!
Key Observation: Heap Sort Connection
Important pattern: Repeatedly calling remove() on a max-heap returns elements in descending order (largest to smallest).
For a min-heap, remove() would return elements in ascending order (smallest to largest).
This is the foundation of Heap Sort! (We'll explore this in a later lecture.)
Example 2: Best-Case Remove Scenario
What's the best case for remove?
When the last element moved to root, there is no violation requiring zero swaps.
Initial:
[90]
/ \
/ \
[30] [40]
Array: [90, 30, 40]
0 1 2
Remove 90:
──────────
Step 1: Save 90
Step 2: Replace root with last element (40)
Step 3: Decrease size to 2
[40]
/
/
[30]
Array: [40, 30]
0 1
Bubble-down:
────────────
Compare: 40 > 30 → No need to swap → Stop
Total swaps: 0
Best case achieved!
Best-case requirement: The last element must be the second best element, so no swaps are needed.
Example 3: Worst-Case Remove Scenario
What's the worst case?
When the last element (moved to root) is smaller than all elements in the heap, requiring it to bubble down all the way to a leaf.
Initial heap (height 2):
[90]
/ \
/ \
[80] [70]
/ \ / \
/ \ / \
[75] [77] [65] [10] ← Last element is smallest!
Array: [90, 80, 70, 75, 77, 65, 10]
0 1 2 3 4 5 6
Remove 90:
──────────
Replace root with 10:
[10]
/ \
/ \
[80] [70]
/ \ /
/ \ /
[75] [77] [65]
Bubble-down:
────────────
Iteration 1: 10 at index 0
Children: 80 and 70
Larger child: 80
Compare: 10 < 80 → Swap
[80]
/ \
/ \
[10] [70]
/ \ /
/ \ /
[75] [77] [65]
Iteration 2: 10 at index 1
Children: 75 and 77
Larger child: 77
Compare: 10 < 77 → Swap
[80]
/ \
/ \
[77] [70]
/ \ /
/ \ /
[75] [10] [65]
Iteration 3: 10 at index 4
No children → Stop
Total swaps: 2 = height of tree
The element traveled the maximum distance!
Worst-case pattern: The last element is smallest, requiring swaps all the way down. Number of swaps = height = O(log n).
Summary of Remove Patterns
Number of swaps in remove():
- Best case: 0 swaps (last element is already large enough)
- Average case: ~log n / 2 swaps (stops midway down)
- Worst case: log n swaps (last element bubbles to leaf)
On the next page, we'll explore the Java Comparator interface, which provides flexibility in defining priorities beyond the natural ordering.