Module A-1·12 min read

Min-heap and max-heap structure, heapify, and O(log n) insertion/extraction as a priority queue.

Written by Jatin Jain Saraf · Architect of SupraScan

Module A-1 — Heaps: Min-Heap, Max-Heap, and Heapify

What this module covers: A heap is a binary tree (Module P-4) with one structural guarantee a BST (Module P-5) doesn't have: it's always a complete tree, which means its height is always O(log n), regardless of insertion order — no degeneration possible, unlike the BST worst case. This module covers how that guarantee is implemented (as an array, with no pointers at all), insertion and extraction, and why a heap is the structure behind every priority queue.

The Heap Property and Completeness

A heap enforces one rule at every node — the heap property: in a min-heap, every parent is smaller than or equal to both its children; in a max-heap, every parent is larger than or equal to both its children. Note what this rule does not require: there's no left-smaller-right-larger ordering between siblings, the way a BST requires (Module P-5) — only a parent-to-child relationship.

Min-Heap:
        2
       / \
      5   3
     / \  /
    8  9 7

The second guarantee — completeness — is what makes heaps structurally different from a BST: every level of the tree is completely filled, except possibly the last level, which fills strictly left to right with no gaps. This isn't a property that depends on the order values happen to be inserted in (unlike a BST, where sorted-order insertion produces a degenerate, linear tree per Module P-5) — completeness is a structural invariant the insert and extract operations actively maintain on every single operation, which is exactly why a heap's height is always O(log n), with no adversarial-input failure mode to worry about.

No Pointers Needed: The Array Representation

Because a heap is always complete, its shape is entirely predictable — which means it can be stored as a plain array, with parent/child relationships computed by arithmetic instead of left/right pointers (Module P-4, P-5):

function parentIndex(i: number): number { return Math.floor((i - 1) / 2); }
function leftChildIndex(i: number): number { return 2 * i + 1; }
function rightChildIndex(i: number): number { return 2 * i + 2; }

This is a direct callback to Module F-2: array indexing is O(1), and because a heap's shape is always predictable (complete, filling left to right), every node's parent and children can be found by pure arithmetic on its index — no node object, no left/right fields, no pointer-chasing at all. This is a meaningfully more compact representation than the tree node classes from Modules P-4 and P-5.

Insert: Add at the End, Then Bubble Up

class MinHeap {
  private heap: number[] = [];
 
  insert(value: number): void {
    this.heap.push(value); // add at the very end — the next available slot, keeping completeness
    this.bubbleUp(this.heap.length - 1);
  }
 
  private bubbleUp(index: number): void {
    while (index > 0) {
      const parent = parentIndex(index);
      if (this.heap[parent] <= this.heap[index]) break; // heap property already satisfied — stop
      [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]]; // swap upward
      index = parent;
    }
  }
}

Adding at the end of the array preserves completeness automatically (it's always the correct next slot in a left-to-right-filling complete tree). The new value might now violate the heap property relative to its parent, so bubbleUp repeatedly swaps it upward until either it reaches the root or finds a parent it's no longer smaller than. Since the tree's height is O(log n) (guaranteed by completeness), this swap-upward chain can happen at most O(log n) times — insertion is O(log n), full stop, with no worst-case degradation possible.

Extract-Min: Swap, Remove, Bubble Down

class MinHeap {
  // ...(insert/bubbleUp above)
 
  extractMin(): number | undefined {
    if (this.heap.length === 0) return undefined;
 
    const min = this.heap[0];
    const last = this.heap.pop()!; // Module F-2 — O(1), removing from the end
 
    if (this.heap.length > 0) {
      this.heap[0] = last; // move the last element to the root...
      this.bubbleDown(0);  // ...then restore the heap property from the top down
    }
 
    return min;
  }
 
  private bubbleDown(index: number): void {
    while (true) {
      const left = leftChildIndex(index);
      const right = rightChildIndex(index);
      let smallest = index;
 
      if (left < this.heap.length && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < this.heap.length && this.heap[right] < this.heap[smallest]) smallest = right;
 
      if (smallest === index) break; // heap property satisfied here — stop
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}