Command Palette

Search for a command to run...

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:

Text Editor
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:

ValueSwapsReason
500First element (root)
300Smaller than parent
701Larger than parent, bubbled to root
200Smaller than parent
601Larger than parent, stopped at grandparent
802Largest so far, bubbled all the way to root
100Smaller than parent

Pattern observed: The number of swaps depends on:

  1. How large the inserted value is relative to its ancestors
  2. 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.

Text Editor
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:

Text Editor
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.

Text Editor
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.

Text Editor
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:

  1. Number of swaps ≤ height of tree - worst case is bubbling to the root
  2. Zero swaps is common - happens whenever inserted value is smaller than parent
  3. Each swap moves up exactly one level - corresponds to one level in the tree
  4. 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.