Heaps & Priority Queues

A heap is a complete binary tree stored in an array that satisfies the heap property: in a min-heap every parent is smaller than or equal to its children; in a max-heap every parent is larger than or equal to its children. JavaScript ships with no built-in priority queue — you must implement one. That implementation, and the patterns built on top of it, appear constantly in FAANG interviews.

What Is a Heap

A complete binary tree has every level fully filled except possibly the last, which is filled strictly left-to-right. This guarantees height exactly floor(log₂ n) for n nodes.

Array Representation

The complete binary tree maps perfectly onto a flat array — no pointers needed:

• Node at index i has its parent at Math.floor((i - 1) / 2)
• Left child at 2 * i + 1
• Right child at 2 * i + 2

Min-heap:        1
                / \
               3   2
              / \ / \
             7  4 5  6

Array: [1, 3, 2, 7, 4, 5, 6]
         0  1  2  3  4  5  6

Min-heap property: heap[parent] <= heap[child] for every node. Max-heap property: heap[parent] >= heap[child] for every node.

The root is always at index 0 and always holds the global minimum (min-heap) or maximum (max-heap).

Core Operations

Why O(log n) for insert/extract? The tree height is floor(log₂ n). Sift-up and sift-down traverse at most one root-to-leaf path, swapping at each level. The number of swaps is therefore bounded by the height.

Complete MinHeap Implementation

JavaScript has no built-in heap. Every interview that requires one expects you to write it from scratch or simulate it. Know this cold.

class MinHeap {
  private heap: number[] = [];

  get size(): number { return this.heap.length; }
  peek(): number | undefined { return this.heap[0]; }

  insert(val: number): void {
    this.heap.push(val);
    this.heapifyUp(this.heap.length - 1);
  }

  extractMin(): number | undefined {
    if (this.heap.length === 0) return undefined;
    const min = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.heapifyDown(0);
    }
    return min;
  }

  private heapifyUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  private heapifyDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < n && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < n && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest === i) break;
      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
      i = smallest;
    }
  }
}

Generic Heap with Custom Comparator

For interview problems you need to store objects and sort by a custom key. A generic heap with a comparator handles both min-heaps and max-heaps:

class Heap<T> {
  private data: T[] = [];

  constructor(private cmp: (a: T, b: T) => number) {}

  get size(): number { return this.data.length; }
  peek(): T | undefined { return this.data[0]; }

  push(val: T): void {
    this.data.push(val);
    let i = this.data.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.cmp(this.data[p], this.data[i]) <= 0) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }

  pop(): T | undefined {
    if (!this.data.length) return undefined;
    const top = this.data[0];
    const last = this.data.pop()!;
    if (this.data.length > 0) {
      this.data[0] = last;
      let i = 0;
      while (true) {
        let best = i;
        const l = 2 * i + 1, r = 2 * i + 2;
        if (l < this.data.length && this.cmp(this.data[l], this.data[best]) < 0) best = l;
        if (r < this.data.length && this.cmp(this.data[r], this.data[best]) < 0) best = r;
        if (best === i) break;
        [this.data[best], this.data[i]] = [this.data[i], this.data[best]];
        i = best;
      }
    }
    return top;
  }
}

// Min-heap of numbers:
const minH = new Heap<number>((a, b) => a - b);
// Max-heap of numbers:
const maxH = new Heap<number>((a, b) => b - a);
// Min-heap by object field:
const byFreq = new Heap<[string, number]>((a, b) => a[1] - b[1]);

Building a Heap in O(n) — Linear Heapify

Naïve approach: insert n elements one at a time → O(n log n).

Linear heapify: start from the last internal node (index Math.floor(n/2) - 1) and sift-down toward the root. Leaf nodes are already valid heaps of size 1.

function buildHeap(arr: number[]): void {
  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
    heapifyDown(arr, i, arr.length);
  }
}

Why O(n)? A node at height h can sift down at most h levels. There are at most n / 2^(h+1) nodes at height h. Total work:

T(n) = Σ (h=0 to log n)  h × n / 2^(h+1)
     = n/2 × Σ (h=0 to ∞)  h / 2^h
     = n/2 × 2              ← series Σ h·(1/2)^h = (1/2)/(1/2)² = 2
     = O(n)

The insight: most nodes sit near the leaves where height is small. The few nodes near the root are expensive but there are only O(1) of them. The series converges and total work is linear.

Max-Heap

Flip the comparator — everything else is identical:

const maxHeap = new Heap<number>((a, b) => b - a);

When using language-native heaps (Java PriorityQueue, Python heapq) that only support min-heaps, negate values: push -val, pop and negate the result.

Pattern: Top-K Elements

K Largest Elements — Min-Heap of Size K

Maintain a min-heap of exactly K elements. For each new element, push it; if the heap exceeds K, pop the minimum. The heap always retains the K largest seen so far.

Why a min-heap? The heap root is the weakest (smallest) of the K candidates. If a new element beats it, evict it. If not, ignore the new element.

function kLargest(nums: number[], k: number): number[] {
  const heap = new Heap<number>((a, b) => a - b); // min-heap
  for (const n of nums) {
    heap.push(n);
    if (heap.size > k) heap.pop(); // evict the smallest
  }
  const result: number[] = [];
  while (heap.size) result.push(heap.pop()!);
  return result; // ascending order; reverse for descending
}
// Time: O(n log k)   Space: O(k)
// Beats sorting when k << n: O(n log k) vs O(n log n)

K Smallest Elements — Max-Heap of Size K

Symmetric: maintain a max-heap of size K. Evict the max when the heap exceeds K.

function kSmallest(nums: number[], k: number): number[] {
  const heap = new Heap<number>((a, b) => b - a); // max-heap
  for (const n of nums) {
    heap.push(n);
    if (heap.size > k) heap.pop();
  }
  const result: number[] = [];
  while (heap.size) result.push(heap.pop()!);
  return result; // descending order
}

Kth Largest Element in a Stream — LC 703

Maintain a min-heap of size K. The root is always the Kth largest seen so far.

class KthLargest {
  private heap: Heap<number>;

  constructor(private k: number, nums: number[]) {
    this.heap = new Heap<number>((a, b) => a - b);
    for (const n of nums) this.add(n);
  }

  add(val: number): number {
    this.heap.push(val);
    if (this.heap.size > this.k) this.heap.pop();
    return this.heap.peek()!;
  }
}
// Time per add: O(log k)   Space: O(k)

Pattern: Merge K Sorted Arrays — O(n log k)

Each list contributes its current minimum. Use a min-heap keyed by value. Always extend the list that just contributed.

function mergeKSorted(arrays: number[][]): number[] {
  // Heap entry: [value, arrayIndex, elementIndex]
  type Entry = [number, number, number];
  const heap = new Heap<Entry>((a, b) => a[0] - b[0]);

  for (let i = 0; i < arrays.length; i++) {
    if (arrays[i].length > 0) heap.push([arrays[i][0], i, 0]);
  }

  const result: number[] = [];
  while (heap.size > 0) {
    const [val, ai, ei] = heap.pop()!;
    result.push(val);
    if (ei + 1 < arrays[ai].length) {
      heap.push([arrays[ai][ei + 1], ai, ei + 1]);
    }
  }
  return result;
}
// Time: O(n log k)  where n = total elements across all arrays, k = number of arrays
// Space: O(k) for the heap, O(n) for output

The same pattern solves Merge K Sorted Lists (LC 23) — store [node.val, listIndex, node] in the heap.

Pattern: Task Scheduler — LC 621

Given tasks with a cooldown of n cycles between identical task types, find the minimum total time to finish all tasks.

Strategy: greedily execute the most-frequent available task at each time step. A max-heap of remaining frequencies tracks what’s available. A queue tracks tasks in their cooldown period.

function leastInterval(tasks: string[], n: number): number {
  const freqMap = new Map<string, number>();
  for (const t of tasks) freqMap.set(t, (freqMap.get(t) ?? 0) + 1);

  const maxH = new Heap<number>((a, b) => b - a); // max-heap of frequencies
  for (const f of freqMap.values()) maxH.push(f);

  let time = 0;
  // [remaining_freq, available_at] — task is available again when time > available_at
  const cooldown: [number, number][] = [];

  while (maxH.size > 0 || cooldown.length > 0) {
    time++;
    // Release tasks whose cooldown has expired before this step
    if (cooldown.length > 0 && cooldown[0][1] < time) {
      maxH.push(cooldown.shift()![0]);
    }
    // Execute the most frequent available task, or idle
    if (maxH.size > 0) {
      const remaining = maxH.pop()! - 1;
      if (remaining > 0) cooldown.push([remaining, time + n]);
    }
    // If heap is empty we idle (time still increments — that's the point)
  }
  return time;
}
// Time: O(total_tasks × log 26) = O(total_tasks)  — at most 26 distinct tasks
// Space: O(1) — cooldown queue and heap bounded by alphabet size

Pattern: Find Median from Data Stream — LC 295

Two-heap trick: split numbers into a lower half and upper half.

• lo = max-heap of lower half → its root is the largest of the smaller numbers
• hi = min-heap of upper half → its root is the smallest of the larger numbers
• Invariant: lo.size == hi.size or lo.size == hi.size + 1

The median is either lo.peek() (odd total) or the average of both roots (even total).

class MedianFinder {
  private lo = new Heap<number>((a, b) => b - a); // max-heap: lower half
  private hi = new Heap<number>((a, b) => a - b); // min-heap: upper half

  addNum(num: number): void {
    // Always push to lo first, then rebalance
    this.lo.push(num);

    // Ensure every element in lo is <= every element in hi
    if (this.hi.size > 0 && this.lo.peek()! > this.hi.peek()!) {
      this.hi.push(this.lo.pop()!);
    }

    // Keep lo either equal in size or one larger than hi
    if (this.lo.size > this.hi.size + 1) {
      this.hi.push(this.lo.pop()!);
    } else if (this.hi.size > this.lo.size) {
      this.lo.push(this.hi.pop()!);
    }
  }

  findMedian(): number {
    if (this.lo.size > this.hi.size) return this.lo.peek()!;
    return (this.lo.peek()! + this.hi.peek()!) / 2;
  }
}
// addNum: O(log n)   findMedian: O(1)   Space: O(n)

Heap Sort — O(n log n) In-Place

1. Build a max-heap in O(n).
2. Swap the root (maximum) with the last element, shrink the heap by 1, sift-down the new root.
3. Repeat until only one element remains.

function heapSort(arr: number[]): void {
  const n = arr.length;

  // Phase 1: build max-heap in O(n)
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(arr, i, n);

  // Phase 2: extract elements largest-first into sorted position
  for (let end = n - 1; end > 0; end--) {
    [arr[0], arr[end]] = [arr[end], arr[0]]; // move current max to end
    siftDown(arr, 0, end);                   // restore heap for remaining
  }
}

function siftDown(arr: number[], i: number, size: number): void {
  while (true) {
    let largest = i;
    const l = 2 * i + 1, r = 2 * i + 2;
    if (l < size && arr[l] > arr[largest]) largest = l;
    if (r < size && arr[r] > arr[largest]) largest = r;
    if (largest === i) break;
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    i = largest;
  }
}
// Time: O(n log n)   Space: O(1) — in-place, NOT stable

Heap sort has the same asymptotic complexity as merge sort but is in-place. It’s not stable (equal elements may swap), and it has worse cache performance than quicksort in practice — so it’s rarely used in production but is a common interview topic.

Full Complexity Reference

When to Reach for a Heap

• “Top K anything” → heap of size K, O(n log k) beats O(n log n) sorting
• “Kth largest / smallest” → min/max-heap of size K
• “Continuously find min or max” as new data arrives → heap
• “Merge K sorted” structures → min-heap with one entry per list
• “Greedy scheduling” (most frequent, earliest deadline, shortest job) → max-heap of frequencies or min-heap of deadlines
• “Median of a stream” → two heaps (lower-half max-heap + upper-half min-heap)

Interview red flag: sorting an entire array just to pull the min or max repeatedly. That’s O(n log n) when a heap gives O(n + k log n). If you catch yourself calling .sort() for a streaming or incremental problem, reach for a heap instead.