HeapsLesson 2

Heap Operations

Insert (bubble up) and extract-min/max (bubble down) — the two core operations that maintain the heap property, step by step.

What Is It?

Now that you understand what a heap is, let's look at the operations that make it useful. There are four:

INSERT: Add a new value and fix the heap
EXTRACT-MAX: Remove the largest value (the root) and fix the heap
PEEK: Look at the largest value without removing it — always instant
BUILD-HEAP: Turn any array into a valid heap efficiently

The core fixing mechanisms are sift up and sift down. When something is out of place, you either bubble it upward (sift up) or push it downward (sift down) until the heap rule is restored.

Analogy

The Tournament Bracket

Imagine a single-elimination tournament. The best player wins every match and sits at the top. The heap is always in this "champion at the top" state.

INSERT is like adding a new player. They start at the bottom and play their way up — challenge their parent, win (if they're bigger), swap positions, and keep going until they lose or reach the top. This is sift up.

EXTRACT-MAX is like the champion retiring. You can't leave the top empty, so you grab the very last player in the tournament and put them at the top temporarily. Obviously they don't belong there. They play against both their children — the stronger child challenges them, and if they lose, they move down. This repeats until they're in the right spot. This is sift down.

How It Works

SIFT UP

Sift up moves a node upward until it's in the right spot. Used when you add a new value.

pseudocode

function siftUp(index):
    while index > 0:
        parentIdx = (index - 1) / 2
        if array[index] > array[parentIdx]:   // Child is bigger than parent
            swap(index, parentIdx)
            index = parentIdx
        else:
            break                             // Heap property is satisfied

Keep swapping with the parent until the parent is bigger (or we reach the root).

INSERT

Add the value at the end of the array (to keep the tree complete), then sift it up:

pseudocode

function insert(value):
    array.append(value)    // Add at the end
    size = size + 1
    siftUp(size - 1)       // Bubble it up to its correct spot

Step-by-step: INSERT(85)

pseudocode

Starting heap: [90, 70, 80, 50, 60, 40]
          90
         /  \
       70    80
      / \    /
    50  60  40
Step 1: Append 85 at the end
  Array: [90, 70, 80, 50, 60, 40, 85]
  85 is at index 6
          90
         /  \
       70    80
      / \    / \
    50  60  40  85
Step 2: siftUp(6)
  parent of 6 = (6-1)/2 = 2  -> value 80
  85 > 80? YES -> swap index 6 and index 2
  Array: [90, 70, 85, 50, 60, 40, 80]
          90
         /  \
       70    85
      / \    / \
    50  60  40  80
Step 3: siftUp(2)
  parent of 2 = (2-1)/2 = 0  -> value 90
  85 > 90? NO -> stop
Final: [90, 70, 85, 50, 60, 40, 80]
85 found its correct position.

SIFT DOWN

Sift down pushes a node downward until it's in the right spot. Used when you remove the root.

pseudocode

function siftDown(index):
    while true:
        largest = index
        left = 2 * index + 1
        right = 2 * index + 2
        
        if left < size and array[left] > array[largest]:
            largest = left
        if right < size and array[right] > array[largest]:
            largest = right
        
        if largest != index:
            swap(index, largest)
            index = largest
        else:
            break    // Heap property satisfied

Compare the current node with both children. Swap with the LARGER child (so it becomes the new parent and is bigger than the other child). Keep going until neither child is bigger.

EXTRACT-MAX

Remove and return the root. Replace it with the last element, then sift it down:

pseudocode

function extractMax():
    if size == 0:
        error "Heap is empty"
    
    maxValue = array[0]          // Save the max
    array[0] = array[size - 1]   // Move last element to root
    size = size - 1
    array.removeLast()
    
    if size > 0:
        siftDown(0)              // Push the new root down to its right spot
    
    return maxValue

Step-by-step: EXTRACT-MAX

pseudocode

Starting heap: [90, 70, 85, 50, 60, 40, 80]
          90
         /  \
       70    85
      / \    / \
    50  60  40  80
Step 1: Save max = 90. Move last element (80) to root.
  Array: [80, 70, 85, 50, 60, 40]
          80
         /  \
       70    85
      / \    /
    50  60  40
Step 2: siftDown(0)
  left = 1 (value 70), right = 2 (value 85)
  largest is index 2 (85 is biggest of 80, 70, 85)
  swap index 0 and index 2
  Array: [85, 70, 80, 50, 60, 40]
          85
         /  \
       70    80
      / \    /
    50  60  40
Step 3: siftDown(2)  (80 moved here)
  left = 5 (value 40), right = 6 (beyond array)
  largest is still 2 (80 > 40)
  No swap needed. Stop.
Final: [85, 70, 80, 50, 60, 40]
Returned 90. New max is 85.

PEEK

Simply return the first element. Always O(1).

pseudocode

function peek():
    if size == 0:
        error "Heap is empty"
    return array[0]

BUILD-HEAP: Turning Any Array into a Heap

You have a random array and want to make it a heap. You could insert each element one by one, but there's a faster way.

The key insight: leaf nodes are already valid heaps on their own. So start from the last non-leaf node and sift it down. Then move backward toward the root, sifting each node down.

pseudocode

function buildHeap(inputArray):
    array = inputArray
    size = length(array)
    
    // Start from the last non-leaf node and go backwards to the root
    for i = (size / 2 - 1) down to 0:
        siftDown(i)

Step-by-step: BUILD-HEAP

pseudocode

Input: [30, 50, 80, 40, 90, 60, 70]
As a tree:
          30
         /  \
       50    80
      / \    / \
    40  90  60  70
size = 7
Last non-leaf: index 7/2 - 1 = 2 (value 80)
Leaves are at indices 3, 4, 5, 6 — skip them
Step 1: siftDown(2)  (value 80)
  left = 5 (60), right = 6 (70)
  80 >= 70 and 80 >= 60 -> no swap needed
          30
         /  \
       50    80
      / \    / \
    40  90  60  70
Step 2: siftDown(1)  (value 50)
  left = 3 (40), right = 4 (90)
  90 is the largest of 50, 40, 90 -> swap index 1 and 4
          30
         /  \
       90    80
      / \    / \
    40  50  60  70
  Continue siftDown from index 4 (value 50)
  left = 9 (beyond array) -> no children, stop
Step 3: siftDown(0)  (value 30)
  left = 1 (90), right = 2 (80)
  90 is largest -> swap index 0 and 1
          90
         /  \
       30    80
      / \    / \
    40  50  60  70
  Continue siftDown from index 1 (value 30)
  left = 3 (40), right = 4 (50)
  50 is largest -> swap index 1 and 4
          90
         /  \
       50    80
      / \    / \
    40  30  60  70
  Continue siftDown from index 4 (value 30)
  left = 9 (beyond array) -> stop
Final: [90, 50, 80, 40, 30, 60, 70]
Verify: 90>=50, 90>=80, 50>=40, 50>=30, 80>=60, 80>=70. Valid!

This approach is O(n) — much better than inserting one by one which is O(n log n). Why? Because most nodes are near the bottom and need very few swaps. Leaves (half the nodes) need zero swaps. Only the root may need up to log(n) swaps.

The Full MaxHeap Class

pseudocode

class MaxHeap:
    array = []
    size = 0
    
    function siftUp(index):
        while index > 0:
            p = (index - 1) / 2
            if array[index] > array[p]:
                swap(index, p)
                index = p
            else:
                break
    
    function siftDown(index):
        while true:
            largest = index
            left = 2 * index + 1
            right = 2 * index + 2
            if left < size and array[left] > array[largest]:
                largest = left
            if right < size and array[right] > array[largest]:
                largest = right
            if largest != index:
                swap(index, largest)
                index = largest
            else:
                break
    
    function insert(value):
        array.append(value)
        size = size + 1
        siftUp(size - 1)
    
    function extractMax():
        if size == 0: error "empty"
        maxVal = array[0]
        array[0] = array[size - 1]
        size = size - 1
        array.removeLast()
        if size > 0: siftDown(0)
        return maxVal
    
    function peek():
        return array[0]
    
    function buildHeap(inputArray):
        array = inputArray
        size = length(array)
        for i = (size / 2 - 1) down to 0:
            siftDown(i)

Time Complexity

Insert— sift up at most h levels

O(log n)

Extract-Max— sift down at most h levels

O(log n)

Peek— just return array[0]

O(1)

Build-Heap— bottom-up sift-down trick

O(n)

Examples

Example 1: Series of insertions

pseudocode

Insert 40, 50, 30, 80, 60 into an empty heap:
Insert 40: [40]
Insert 50: [40, 50]
  siftUp(1): 50 > 40 -> swap
  [50, 40]
Insert 30: [50, 40, 30]
  siftUp(2): 30 < 50 -> stop
Insert 80: [50, 40, 30, 80]
  siftUp(3): 80 > 40 -> swap -> [50, 80, 30, 40]
  siftUp(1): 80 > 50 -> swap -> [80, 50, 30, 40]
Insert 60: [80, 50, 30, 40, 60]
  siftUp(4): 60 > 50 -> swap -> [80, 60, 30, 40, 50]
  siftUp(1): 60 < 80 -> stop
Final tree:
        80
       / \
      60  30
     / \
    40  50

Example 2: Extract-max twice

pseudocode

Heap: [80, 60, 30, 40, 50]
Extract-max #1:
  Remove 80. Move 50 to root. [50, 60, 30, 40]
  siftDown(0): 60 is largest child -> swap
  [60, 50, 30, 40]
  siftDown(1): 50 > 40 -> stop
  Heap: [60, 50, 30, 40]
Extract-max #2:
  Remove 60. Move 40 to root. [40, 50, 30]
  siftDown(0): 50 is largest child -> swap
  [50, 40, 30]
  Heap: [50, 40, 30]

Example 3: Heapsort in a nutshell

Extract-max repeatedly gives you values in descending order:

pseudocode

Extract all from [80, 60, 30, 40, 50]:
  80, 60, 50, 40, 30
Reverse it -> 30, 40, 50, 60, 80  -- sorted!

Build a heap in O(n), extract everything in O(n log n). Total: O(n log n) sort with no extra space.

Common Mistakes

Swapping with the wrong child in sift down. Always swap with the LARGER child. If you swap with the smaller one, the new parent won't be bigger than the other child, breaking the heap.

Forgetting bounds checks. Before comparing with a child, check that the child index is within bounds (left < size). The last non-leaf node might have only a left child.

Mixing up sift up and sift down. INSERT uses sift UP (new value bubbles up from the bottom). EXTRACT uses sift DOWN (replacement value sinks from the top). Getting them backwards breaks everything.

Starting build-heap from the wrong end. Build-heap starts from the LAST non-leaf node (index size/2 - 1) and works backward to 0. Starting from 0 and going forward gives you O(n log n) instead of O(n).

Best Practices

Use build-heap when you have all elements upfront — it's O(n) vs O(n log n) for repeated inserts
Write siftUp and siftDown as separate helper functions — every other operation uses them
For a min-heap, flip all comparisons: change > to < in siftUp and siftDown. Everything else stays the same
When you need the k largest elements from a large collection, use a min-heap of size k — the min at the top tells you what to drop when a larger value arrives

How Heaps Work What Is a Graph?