Tracing Insert Operations
Let's trace complete insertion sequences to build intuition for how bubble-up maintains the heap property.
Example 1: Building a Heap from Scratch
Task: Insert the sequence: 50, 30, 70, 20, 60, 80, 10
Starting with empty heap:
Insert 50:
────────
Array: [50]
0
Tree: [50]
No parent, no bubble-up needed.
Insert 30:
────────
Step 1: Add at end (index 1)
Array: [50, 30]
0 1
Tree: [50]
/
[30]
Step 2: Check 30 vs parent 50
30 < 50 ✓ Already satisfies heap property
No swaps needed
Final: [50]
/
[30]
Insert 70:
────────
Step 1: Add at end (index 2)
Array: [50, 30, 70]
0 1 2
Tree: [50]
/ \
[30] [70]
Step 2: Check 70 vs parent 50
70 > 50 ✗ Violation! Swap them
After swap:
Array: [70, 30, 50]
0 1 2
Tree: [70]
/ \
[30] [50]
Step 3: Check 70 vs its new parent (none - at root)
At root, stop
Final: [70]
/ \
[30] [50]
Insert 20:
────────
Step 1: Add at end (index 3)
Array: [70, 30, 50, 20]
0 1 2 3
Tree: [70]
/ \
[30] [50]
/
[20]
Step 2: Check 20 vs parent 30
20 < 30 ✓ Already satisfies heap property
No swaps needed
Final: [70]
/ \
[30] [50]
/
[20]
Insert 60:
────────
Step 1: Add at end (index 4)
Array: [70, 30, 50, 20, 60]
0 1 2 3 4
Tree: [70]
/ \
[30] [50]
/ \
[20][60]
Step 2: Check 60 vs parent 30
60 > 30 ✗ Violation! Swap them
After swap:
Array: [70, 60, 50, 20, 30]
0 1 2 3 4
Tree: [70]
/ \
[60] [50]
/ \
[20][30]
Step 3: Check 60 vs its new parent 70
60 < 70 ✓ Heap property satisfied
Stop
Final: [70]
/ \
[60] [50]
/ \
[20][30]
Insert 80:
────────
Step 1: Add at end (index 5)
Array: [70, 60, 50, 20, 30, 80]
0 1 2 3 4 5
Tree: [70]
/ \
[60] [50]
/ \ /
[20][30] [80]
Step 2: Check 80 vs parent 50
80 > 50 ✗ Violation! Swap them
After first swap:
Array: [70, 60, 80, 20, 30, 50]
0 1 2 3 4 5
Tree: [70]
/ \
[60] [80]
/ \ /
[20][30] [50]
Step 3: Check 80 vs its new parent 70
80 > 70 ✗ Still violates! Swap them
After second swap:
Array: [80, 60, 70, 20, 30, 50]
0 1 2 3 4 5
Tree: [80]
/ \
[60] [70]
/ \ /
[20][30] [50]
Step 4: Check 80 vs its new parent (none - at root)
At root, stop
Final: [80]
/ \
[60] [70]
/ \ /
[20][30] [50]
Insert 10:
────────
Step 1: Add at end (index 6)
Array: [80, 60, 70, 20, 30, 50, 10]
0 1 2 3 4 5 6
Tree: [80]
/ \
[60] [70]
/ \ / \
[20][30] [50][10]
Step 2: Check 10 vs parent 70
10 < 70 ✓ Already satisfies heap property
No swaps needed
Final: [80]
/ \
[60] [70]
/ \ / \
[20][30] [50][10]
Analysis of the Sequence
Number of swaps per insertion:
| Value | Swaps | Reason |
|---|---|---|
| 50 | 0 | First element (root) |
| 30 | 0 | Smaller than parent |
| 70 | 1 | Larger than parent, bubbled to root |
| 20 | 0 | Smaller than parent |
| 60 | 1 | Larger than parent, stopped at grandparent |
| 80 | 2 | Largest so far, bubbled all the way to root |
| 10 | 0 | Smaller than parent |
Pattern observed: The number of swaps depends on:
- How large the inserted value is relative to its ancestors
- How far from the root it's inserted (tree height at that position)
Example 2: Worst-Case Insertion Scenario
What's the worst case for a single insertion?
Inserting a value larger than all existing elements causes it to bubble all the way to the root.
Start with heap: [50, 40, 30, 20, 10]
Tree: [50]
/ \
[40] [30]
/ \
[20][10]
Height = 2
Insert 60:
────────
Position: index 5 (right child of 30)
Parent distance to root: 2 levels
Swap 1: 60 with 30
Swap 2: 60 with 50
Total swaps: 2 = height of tree
The element travels the entire height!
Worst-case pattern: Inserting values in increasing order into an initially empty heap causes each element to bubble to the root.
Example - Inserting 10, 20, 30, 40, 50:
Insert 10: [10] → 0 swaps
Insert 20: [20, 10] → 1 swap
Insert 30: [30, 10, 20] → 1 swap
Insert 40: [40, 30, 20, 10] → 2 swaps
Insert 50: [50, 40, 20, 10, 30] → 2 swaps
Each new element becomes the new maximum!
Example 3: Best-Case Insertion Scenario
What's the best case?
Inserting a value smaller than its parent requires zero swaps.
Insert 75 into this heap:
Tree: [90]
/ \
[70] [80]
/ \
[50][60]
Array: [90, 70, 80, 50, 60]
New position: index 5 (left child of 80)
Parent: 80
Check: 75 < 80 ✓
Result: 0 swaps! Heap property already satisfied
Final: [90]
/ \
[70] [80]
/ \ /
[50][60] [75]
Best-case pattern: Inserting the smallest value requires no swaps, regardless of tree size.
Visualizing Array vs Tree Operations
Important concept: Each swap in the array corresponds to moving up one level in the tree.
Insert 85 into heap:
Initial state:
Array: [90, 70, 80, 50, 60]
0 1 2 3 4
Tree: [90]
/ \
[70] [80]
/ \
[50][60]
Step 1: Add 85 at index 5
Array: [90, 70, 80, 50, 60, 85]
0 1 2 3 4 5
↑
position
Tree: [90]
/ \
[70] [80]
/ \ /
[50][60] [85] ← level 2
Parent of index 5 = (5-1)/2 = 2
Parent value: heap[2] = 80
Step 2: Compare and swap (85 > 80)
Array: [90, 70, 85, 50, 60, 80]
0 1 2 3 4 5
↑
position moved
Tree: [90]
/ \
[70] [85] ← level 1
/ \ /
[50][60] [80]
Parent of index 2 = (2-1)/2 = 0
Parent value: heap[0] = 90
Step 3: Compare (85 < 90) → Stop
Array index movement: 5 → 2 → stop
Tree level movement: 2 → 1 → stop
Number of swaps: 1
Summary
Key observations from tracing:
- Number of swaps ≤ height of tree - worst case is bubbling to the root
- Zero swaps is common - happens whenever inserted value is smaller than parent
- Each swap moves up exactly one level - corresponds to one level in the tree
- Complete binary tree property - ensures height is O(log n)
These traces demonstrate why insertion is O(log n) in the worst case—the maximum number of swaps equals the height of a complete binary tree with n nodes, which is ⌊log₂ n⌋.
On the next page, we'll see the remove() operation, which is more complex because it requires "bubble down" to restore the heap property.