Heaps and Priority Queues Explained

A heap is a tree-based data structure that gives you constant-time access to the smallest (min-heap) or largest (max-heap) element, with O(log n) insert and delete. Priority queues are almost always implemented with heaps, and the "Top K" family of problems is the most common heap pattern in FAANG interviews.

What Is a Heap?

A binary heap is a complete binary tree where every parent is ≤ its children (min-heap) or ≥ its children (max-heap). The root is always the global min or max. A complete tree can be stored compactly in an array, so heaps need no pointers.

graph TD
    R["[2] root"] --> A["[4]"]
    R --> B["[6]"]
    A --> C["[9]"]
    A --> D["[10]"]
    B --> E["[8]"]
    B --> F["[11]"]
    style R fill:#D97A2B,stroke:#B86418,color:#fff

Array Representation

For a node at index i: its left child is at 2i + 1, right child at 2i + 2, parent at Math.floor((i - 1) / 2). This index math is why heaps use O(1) space on top of the array.

Core Operations

• peek() : return root, O(1)
• push(x) : add to end, sift up until parent is smaller, O(log n)
• pop() : remove root, move last element to root, sift down, O(log n)
• heapify(array) : build from unsorted data in O(n)

// Min-heap template (handle negated values for max-heap)
class MinHeap<T> {
  private data: T[] = [];
  push(v: T) {
    this.data.push(v);
    let i = this.data.length - 1;
    while (i > 0 && this.data[i] < this.data[(i - 1) >> 1]) {
      [this.data[i], this.data[(i - 1) >> 1]] = [this.data[(i - 1) >> 1], this.data[i]];
      i = (i - 1) >> 1;
    }
  }
  pop(): T | undefined {
    if (this.data.length === 0) return undefined;
    const top = this.data[0];
    const last = this.data.pop()!;
    if (this.data.length) {
      this.data[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let smallest = i;
        if (l < this.data.length && this.data[l] < this.data[smallest]) smallest = l;
        if (r < this.data.length && this.data[r] < this.data[smallest]) smallest = r;
        if (smallest === i) break;
        [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
        i = smallest;
      }
    }
    return top;
  }
}

The Top K Pattern

Top K problems ask for the K largest, smallest, or most frequent elements. The trick is to keep a heap of size K so memory stays O(K) instead of O(n).

// Top K Frequent Elements (min-heap of size K)
function topKFrequent(nums: number[], k: number): number[] {
  const counts = new Map<number, number>();
  for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
  const minHeap: [number, number][] = []; // [freq, num]
  const push = (v: [number, number]) => {
    minHeap.push(v);
    let i = minHeap.length - 1;
    while (i > 0 && minHeap[i][0] < minHeap[(i - 1) >> 1][0]) {
      [minHeap[i], minHeap[(i - 1) >> 1]] = [minHeap[(i - 1) >> 1], minHeap[i]];
      i = (i - 1) >> 1;
    }
  };
  const pop = (): [number, number] => {
    const top = minHeap[0];
    const last = minHeap.pop()!;
    if (minHeap.length) {
      minHeap[0] = last;
      let i = 0;
      while (true) {
        const l = 2*i+1, r = 2*i+2; let s = i;
        if (l < minHeap.length && minHeap[l][0] < minHeap[s][0]) s = l;
        if (r < minHeap.length && minHeap[r][0] < minHeap[s][0]) s = r;
        if (s === i) break;
        [minHeap[i], minHeap[s]] = [minHeap[s], minHeap[i]];
        i = s;
      }
    }
    return top;
  };
  for (const [num, freq] of counts) {
    push([freq, num]);
    if (minHeap.length > k) pop();
  }
  return minHeap.map(([, num]) => num);
}
// Time: O(n log k), Space: O(n + k)

Choosing Min vs Max

Ask which element must be evicted on overflow. For Top K largest, the smallest of the current K is evicted, so the root must be the smallest : use a min-heap. Invert this for Top K smallest with a max-heap (or store negated values).

Merging K Sorted Lists

Push the head of each list into a min-heap, then repeatedly pop the smallest and push that head's next node. Total complexity is O(N log K) for N total nodes.

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  const minHeap = new MinHeap<ListNode>((a, b) => a.val - b.val);
  for (const l of lists) if (l) minHeap.push(l);
  const dummy = new ListNode(0);
  let tail = dummy;
  while (minHeap.data.length) {
    const node = minHeap.pop()!;
    tail.next = node;
    tail = node;
    if (node.next) minHeap.push(node.next);
  }
  return dummy.next;
}

Median Finder (Two Heaps)

Keep a max-heap for the lower half and a min-heap for the upper half. On insert, add to one side then rebalance so sizes differ by at most 1. The median is the root of the larger heap (or the average of both roots). This solves the running-median stream problem in O(log n) per element.

When to Use a Heap

• You repeatedly need the current min or max (Top K, K smallest, K closest points).
• Merging K sorted arrays or streams.
• Median of a stream, or finding the most recent/heaviest by priority.
• Any scheduler-like problem picking the next "best" item by rank.

Common Mistakes

• Building a heap with push in a loop : heapify is O(n) but n pushes are O(n log n). Know both.
• Using a max-heap for Top K largest : you must evict the smallest, so use a min-heap.
• Forgetting heaps are not sorted : a heap only guarantees the root, not in-order traversal.
• Custom objects without a comparator : numeric comparison breaks; supply comparison by field (freq, distance, timestamp).
• Using a heap when a sorted array suffices : if the data is static, sort once in O(n log n) and index in O(1).

Frequently Asked Questions

Related Tutorials

• Sorting Algorithms : when to sort instead of heap.
• Trees and Graphs : heap internals reuse binary tree ideas.
• Stack and Queue : the other order-sensitive containers.
• Heap practice problems : company-tagged heap questions.