The insert() Operation - Bubble Up (Swim)

Insertion is more complex than best() because we must maintain both heap properties: the structure property (complete binary tree) and the order property (parent ≥ children).

The Two-Phase Strategy

Phase 1: Maintain Structure Property

Add the new element at the next available position
In array terms: append to the end
This automatically preserves the complete binary tree structure

Phase 2: Restore Order Property

The new element might violate the heap property (could be larger than its parent)
Bubble up (swim) the element until the heap property is restored

Phase 1: Insert at Next Position

Since we're using an array representation, insertion starts by placing the new element at the end:

Java

public void insert(T item) {
    // Check if we need to resize (we'll handle this later)
    if (size == heap.length) {
        resize();
    }

    // Phase 1: Add to next available position
    heap[size] = item;
    size++;

    // Phase 2: Bubble up to restore heap property
    bubbleUp(size - 1);
}

Why append to the end? This is the only position that maintains the complete binary tree structure. Recall from Day 41 that complete binary trees fill level-by-level from left to right.

Phase 2: The Bubble-Up Algorithm

After inserting at the end, the new element might be larger than its parent, violating the max-heap property. We fix this by repeatedly swapping with the parent until the heap property is restored.

The bubble-up process:

Start with the newly inserted element (at index size - 1 because we just incremented size)
Compare with its parent
If child > parent: swap them
Repeat from the parent's position
Stop when: child ≤ parent OR we reach the root

Visual Example

Initial heap:
        [90]
       /    \
      /      \
    [75]    [80]
   /   \    /
  /     \  /
[50]  [60][70]

Array: [90, 75, 80, 50, 60, 70]
        0   1   2   3   4   5

Insert 85:
Step 1: Add 85 at the end (index 6)
Array: [90, 75, 80, 50, 60, 70, 85]
        0   1   2   3   4   5   6

        [90]
       /    \
      /      \
    [75]     [80]
   /   \     /   \
  /     \   /     \
[50]  [60] [70] [85]  ← Just inserted

Violation! 85 > 80 (its parent)

Step 2: Bubble up - swap 85 with 80
Array: [90, 75, 85, 50, 60, 70, 80]
        0   1   2   3   4   5   6

        [90]
       /    \
      /      \
    [75]     [85]  ← Moved up
   /   \     /   \
  /     \   /     \
[50]  [60] [70] [80]

Check: 85 < 90 (its new parent) ✓
Heap property restored!

Implementation: bubbleUp()

Java

private void bubbleUp(int index) {
    // Calculate parent index
    int parentIndex = (index - 1) / 2;

    // Keep bubbling while:
    // 1. Not at root (index > 0)
    // 2. Child is greater than parent
    while (index > 0 && heap[index].compareTo(heap[parentIndex]) > 0) {
        // Swap child with parent
        swap(index, parentIndex);

        // Move up to parent's position
        index = parentIndex;
        parentIndex = (index - 1) / 2;
    }
}

private void swap(int i, int j) {
    T temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
}

Parent Index Calculation

Recall from Day 41: For a node at index i (using 0-based indexing):

Parent index: (i - 1) / 2 (integer division)

Example calculations:

Child at index 6:
  parentIndex = (6 - 1) / 2 = 5 / 2 = 2 ✓

Child at index 5:
  parentIndex = (5 - 1) / 2 = 4 / 2 = 2 ✓

Child at index 4:
  parentIndex = (4 - 1) / 2 = 3 / 2 = 1 ✓

Child at index 1:
  parentIndex = (1 - 1) / 2 = 0 / 2 = 0 ✓

Important: Integer division automatically floors the result, giving us the correct parent index.

Termination Conditions

The bubble-up loop terminates when either condition becomes true:

Condition 1: Reached the root (index == 0)

No parent to compare with
Root is the maximum position in the heap

Condition 2: Heap property satisfied (heap[index] ≤ heap[parentIndex])

Child is no longer larger than parent
Heap property is restored

Why termination is guaranteed: Each iteration moves closer to the root. Since the tree has finite height, we must eventually reach the root (worst case) or find a parent that's larger (typical case).

Example: Bubble-Up Terminating Early

Insert 72 into this heap:

Array: [90, 75, 80, 50, 60, 70]
        0   1   2   3   4   5

Step 1: Add 72 at index 6
Array: [90, 75, 80, 50, 60, 70, 72]
        0   1   2   3   4   5   6

        [90]
       /    \
      /      \
    [75]     [80]
   /   \     /   \
  /     \   /     \
[50]  [60] [70] [72]

Step 2: Check 72 vs parent 80
  72 < 80 ✓ Heap property already satisfied!
  Bubble-up stops immediately (0 swaps)

Why "Bubble Up" or "Swim"?

Metaphor 1: Bubbles rising in water

Larger elements "rise" toward the root like bubbles rise in water
Each swap moves the element one level higher

Metaphor 2: Swimming upward

The element "swims" up through the tree
Stops when it can't rise any further (reached equilibrium)

Key Insights

Local comparisons suffice: We only compare with the parent, not with siblings or other ancestors. The heap property guarantees that if we're smaller than our parent, we're also smaller than all ancestors.

Path length determines work: Bubble-up follows a single path from insertion point to (potentially) the root. The number of comparisons and swaps is at most the height of the tree.

Height is logarithmic: Since the heap is a complete binary tree with n elements, its height is ⌊log₂ n⌋. This means bubble-up performs at most O(log n) comparisons and swaps.

Comparison with Other Data Structures

Why insertion is faster than sorted array:

Sorted array: O(n) to shift elements and maintain full sorted order
Binary heap: O(log n) to bubble up and maintain partial order
Key difference: Heaps maintain just enough order to find the maximum quickly, not full sorted order

On the next page, we'll trace complete insertion examples to see bubble-up in action with multiple insertions.

Command Palette