Heap / Priority Queue Complete Guide

Data Structure • hard

Priority queue (usually implemented via heap) always exposes min or max element quickly.

It is ideal when you repeatedly need the next-best candidate rather than full sorting every step.

Many scheduling and shortest-path algorithms depend on priority queues for practical speed.

Typical Complexity Baseline

Metric	Value
Push/pop	`O(log n)`
peek	`O(1)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Min-heap bubble new value up to its rank

Insert at the bottom, then swap with the parent while you are smaller.

Step 1/26Empty min-heap. We'll insert 7 values and watch each bubble up.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Heaps Visually Explained (Priority Queues)

Channel: ByteQuest

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Heap array

What it is Compact tree representation in contiguous array.

Why it matters Heap array is a required building block for understanding how Heap / Priority Queue stays correct and performant on large inputs.

Comparator

What it is Defines min-heap or max-heap ordering.

Why it matters Comparator is a required building block for understanding how Heap / Priority Queue stays correct and performant on large inputs.

Sift-up

What it is Restore heap property after insert.

Why it matters Sift-up is a required building block for understanding how Heap / Priority Queue stays correct and performant on large inputs.

Sift-down

What it is Restore heap property after pop/replace.

Why it matters Sift-down is a required building block for understanding how Heap / Priority Queue stays correct and performant on large inputs.

Heap invariant

What it is Parent priority dominates children.

Why it matters Heap invariant is a required building block for understanding how Heap / Priority Queue stays correct and performant on large inputs.

Min-heap

What it is Smallest key stored at root/top.

Why it matters Smallest key stored at root/top. In Heap / Priority Queue, this definition helps you reason about correctness and complexity when inputs scale.

Max-heap

What it is Largest key stored at root/top.

Why it matters Largest key stored at root/top. In Heap / Priority Queue, this definition helps you reason about correctness and complexity when inputs scale.

Heapify

What it is Build heap from unsorted array in O(n).

Why it matters Build heap from unsorted array in O(n). In Heap / Priority Queue, this definition helps you reason about correctness and complexity when inputs scale.

Top-k

What it is Return k best elements under ranking rule.

Why it matters Return k best elements under ranking rule. In Heap / Priority Queue, this definition helps you reason about correctness and complexity when inputs scale.

Decrease-key

What it is Priority update operation in some heap variants.

Why it matters Priority update operation in some heap variants. In Heap / Priority Queue, this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/26

Empty min-heap. We'll insert 7 values and watch each bubble up.

Step 2/26

Insert 8 at index 0 (next leaf).

Step 3/26

8 reached the root it's the new minimum.

Step 4/26

Insert 5 at index 1 (next leaf).

Step 5/26

Compare with parent arr[0]=8. 5 < 8 → swap.

Step 6/26

After swap: arr = [5, 8]. Now at index 0.

Step 7/26

5 reached the root it's the new minimum.

Step 8/26

Insert 9 at index 2 (next leaf).

Step 9/26

Compare with parent arr[0]=5. 5 ≤ 9 → stop.

Step 10/26

Insert 3 at index 3 (next leaf).

Step 11/26

Compare with parent arr[1]=8. 3 < 8 → swap.

Step 12/26

After swap: arr = [5, 3, 9, 8]. Now at index 1.

Step 13/26

Compare with parent arr[0]=5. 3 < 5 → swap.

Step 14/26

After swap: arr = [3, 5, 9, 8]. Now at index 0.

Step 15/26

3 reached the root it's the new minimum.

Step 16/26

Insert 7 at index 4 (next leaf).

Step 17/26

Compare with parent arr[1]=5. 5 ≤ 7 → stop.

Step 18/26

Insert 1 at index 5 (next leaf).

Step 19/26

Compare with parent arr[2]=9. 1 < 9 → swap.

Step 20/26

After swap: arr = [3, 5, 1, 8, 7, 9]. Now at index 2.

Step 21/26

Compare with parent arr[0]=3. 1 < 3 → swap.

Step 22/26

After swap: arr = [1, 5, 3, 8, 7, 9]. Now at index 0.

Step 23/26

1 reached the root it's the new minimum.

Step 24/26

Insert 6 at index 6 (next leaf).

Step 25/26

Compare with parent arr[2]=3. 3 ≤ 6 → stop.

Step 26/26

Heap built. Each insert is O(log n); building from n inserts is O(n log n) (the heapify-from-array trick is O(n)).

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Sorted array

Choose this when Choose heap for interleaved insert + extract-top operations.

Tradeoff Sorted array is simpler if data is static and query-only.

vs. Hash map

Choose this when Choose heap for ordered-by-priority retrieval.

Tradeoff Hash map cannot return min/max efficiently.

vs. Balanced tree

Choose this when Choose heap for minimal overhead top extraction.

Tradeoff Tree supports ordered iteration and arbitrary deletions better.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Kubernetes

Scheduler-style systems rank candidate nodes/tasks and repeatedly choose the highest-priority next action.

Takeaway Priority queues formalize best-next selection under changing load.

Google Maps

Shortest path variants use min-priority queue to expand nearest frontier first.

Takeaway Heap-driven frontier selection keeps path search efficient.

Apache Kafka ecosystem

Some stream processing jobs use priority queues for watermark/event-time ordering.

Takeaway Priority structures help enforce processing order constraints.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Implement the heap array and sift-up/sift-down operations yourself so enqueue/dequeue behavior is explicit.

Complexity: Push O(log n), Pop O(log n), Peek O(1)

Min-heap priority queue from scratch

Language

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
    }
  }
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

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.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

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.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

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 (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.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Kth Largest Element in a Stream	Easy	`O(log k)`
2	Last Stone Weight	Easy	`O(n log n)`
3	Top K Frequent Elements	Medium	`O(n log k)`
4	K Closest Points to Origin	Medium	`O(n log k)`
5	Task Scheduler	Medium	`O(n log n)`
6	Find K Pairs with Smallest Sums	Medium	`O(k log k)`
7	Merge k Sorted Lists	Hard	`O(n log k)`
8	Find Median from Data Stream	Hard	`O(log n)`
9	IPO	Hard	`O(n log n)`
10	Minimum Number of Refueling Stops	Hard	`O(n log n)`