Heap / Priority Queue Complete Guide

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

How It Compares

Real-World Stories and Company Examples

Min-heap priority queue from scratch

class MinHeap {
  private values: number[] = []

  push(value: number): void {
    this.values.push(value)
    this.siftUp(this.values.length - 1)
  }

  pop(): number | null {
    if (this.values.length === 0) {
      return null
    }

    const rootValue = this.values[0]
    const lastValue = this.values.pop()!
    if (this.values.length > 0) {
      this.values[0] = lastValue
      this.siftDown(0)
    }

    return rootValue
  }

  peek(): number | null {
    return this.values.length > 0 ? this.values[0] : null
  }

  private siftUp(startIndex: number): void {
    let childIndex = startIndex
    while (childIndex > 0) {
      const parentIndex = Math.floor((childIndex - 1) / 2)
      if (this.values[parentIndex] <= this.values[childIndex]) {
        break
      }
      ;[this.values[parentIndex], this.values[childIndex]] = [this.values[childIndex], this.values[parentIndex]]
      childIndex = parentIndex
    }
  }

  private siftDown(startIndex: number): void {
    let parentIndex = startIndex

    while (true) {
      const leftChildIndex = parentIndex * 2 + 1
      const rightChildIndex = parentIndex * 2 + 2
      let smallestIndex = parentIndex

      if (leftChildIndex < this.values.length && this.values[leftChildIndex] < this.values[smallestIndex]) {
        smallestIndex = leftChildIndex
      }
      if (rightChildIndex < this.values.length && this.values[rightChildIndex] < this.values[smallestIndex]) {
        smallestIndex = rightChildIndex
      }
      if (smallestIndex === parentIndex) {
        break
      }

      ;[this.values[parentIndex], this.values[smallestIndex]] = [this.values[smallestIndex], this.values[parentIndex]]
      parentIndex = smallestIndex
    }
  }
}

Common Problems and Failure Modes

• Using wrong comparator direction (min vs max).
• Forgetting stale entries when priorities update externally.
• Assuming heap provides full sorted traversal.
• Inefficient repeated heap rebuilds instead of incremental push/pop.
• Not bounding heap growth in stream systems.

Tips and Tricks

• Use heap when you repeatedly need the next-best element, not full sorting.
• For top-k, min-heap of size k is usually the most memory-efficient pattern.
• When priorities can update, handle stale entries instead of mutating in place.
• Pick min-heap vs max-heap explicitly before implementing comparisons.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

Real-system usage signals

• Fast top element access O(1) with insert/remove O(log n).
• Efficient for top-k, stream merging, and task scheduling.
• Reduces repeated full-sort overhead in iterative workflows.

LeetCode-specific tips (including pattern-identification signals)

• Identification signal: repeatedly choose the current smallest/largest or next-best candidate while new items arrive.
• Identification signal: top-k or streaming ranking appears, where full re-sort each step is too expensive.
• Scheduling, shortest-path frontier expansion, and merge-k workflows usually point to heap/priority-queue.
• For Heap / Priority Queue questions, start by naming the core invariant before writing code.
• Use the constraint section to set time/space target first, then pick the data structure/algorithm.
• Solve one tiny example by hand and map each transition to your variables before implementing.
• Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
• During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.