The remove() Operation - Bubble Down (Sink)

The remove() operation is the most complex heap operation. It must remove the root (highest priority) while maintaining both heap properties.

Key insight: The last element in the array is in the easiest position to remove (no shifting needed). So we:

1. Swap the root with the last element
2. Remove the last element (now contains the old root)
3. Bubble down the new root to restore heap property

This maintains the complete binary tree structure and enables O(log n) removal.

The Three-Phase Algorithm

Phase 1: Save and Return Root

T root = heap[0];  // Save the maximum (to return later)

Phase 2: Replace Root with Last Element

heap[0] = heap[size - 1];  // Move last element to root
heap[size - 1] = null;      // Optional: Help garbage collection
size--;                     // Decrease size (effectively removes last)

Phase 3: Bubble Down to Restore Heap Property

bubbleDown(0);  // Restore heap property starting from root
return root;    // Return the saved maximum

Visual Example

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

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

Step 1: Save root value (90) to return later

Step 2: Replace root with last element (40)
        [40]
       /    \
      /      \
    [75]     [80]
   /   \     /
  /     \   /
[50]  [60] [70]

Array: [40, 75, 80, 50, 60, 70]
        0   1   2   3   4   5
Size decreased from 7 to 6

Violation! 40 < 75 and 40 < 80
Need to bubble down...

Phase 3: The Bubble-Down Algorithm

After moving the last element to the root, it's likely smaller than its children, violating the max-heap property. We fix this by repeatedly swapping with the larger child until the heap property is restored.

The bubble-down process:

1. Start at the root (index 0)
2. Find the larger child
3. If parent < larger child: swap them
4. Repeat from the child's position
5. Stop when: parent ≥ both children OR reached a leaf

Critical decision: Why swap with the larger child?

      [40]
     /    \
   [75]  [80]

If we swap 40 with 75 (smaller child):
      [75]
     /    \
   [40]  [80]

Violation! 75 < 80 (parent smaller than sibling)

Correct: Swap 40 with 80 (larger child):
      [80]
     /    \
   [75]  [40]

✓ 80 > 75 and 80 > 40 (parent greater than both children)

Implementation: bubbleDown()

private void bubbleDown(int index) {
    while (hasLeft(index)) {  // While current node has at least one child
        // Find the larger child
        int largerChildIndex = leftIndex(index);

        // Check if right child exists and is larger than left
        if (hasRight(index) &&
            heap[rightIndex(index)].compareTo(heap[largerChildIndex]) > 0) {
            largerChildIndex = rightIndex(index);
        }

        // Check if heap property is satisfied
        if (heap[index].compareTo(heap[largerChildIndex]) >= 0) {
            break;  // Parent >= larger child, done
        }

        // Swap with larger child
        swap(index, largerChildIndex);
        index = largerChildIndex;  // Move down to child's position
    }
}

Helper Methods for Array Navigation

private int leftIndex(int parentIndex) {
    return 2 * parentIndex + 1;
}

private int rightIndex(int parentIndex) {
    return 2 * parentIndex + 2;
}

private boolean hasLeft(int parentIndex) {
    return leftIndex(parentIndex) < size;
}

private boolean hasRight(int parentIndex) {
    return rightIndex(parentIndex) < size;
}

Why these helpers? They encapsulate the array-to-tree index calculations from Day 41, making the code more readable.

Complete remove() Implementation

Putting it all together:

public T remove() {
    if (isEmpty()) {
        throw new EmptyPriorityQueueException("Cannot remove from empty priority queue");
    }

    // Phase 1: Save root to return
    T root = heap[0];

    // Phase 2: Replace root with last element
    heap[0] = heap[size - 1];
    size--;

    // Phase 3: Bubble down if heap is not empty
    if (size > 0) {
        bubbleDown(0);
    }

    return root;
}

Edge case: If removing the last element (size becomes 0), skip bubble-down—no heap to fix!

Termination Conditions

Bubble-down terminates when either condition is met:

Condition 1: Reached a leaf (no children)

• leftIndex(index) >= size
• No children to swap with

Condition 2: Heap property satisfied

• heap[index] >= heap[largerChild]
• Parent is at least as large as both children

Why termination is guaranteed: Each iteration moves down one level. Since the tree has finite height O(log n), we must eventually reach a leaf or satisfy the heap property.

Handling One Child vs Two Children

Two children: Compare both, swap with larger

One child (only left): Only possible at the last level of a complete binary tree. Swap with the left child if needed.

No children: Node is a leaf, stop immediately

Why only left child is possible: In a complete binary tree, if a node has only one child, it must be a left child (due to left-to-right filling).

Summary

The remove() operation maintains both heap properties through a clever strategy:

• Structure property: Maintained by swapping root with last element
• Order property: Restored by bubbling down the new root

Key insights:

• Swap with last element: Enables O(1) removal while preserving tree structure
• Bubble down: Fixes order property in O(log n) time by following one path
• Choose larger child: Ensures parent ≥ both children after swap

On the next page, we'll trace complete removal sequences to build intuition for bubble-down.