Pattern GuideHeaps (Priority Queues)
Pricing

Heaps (Priority Queues)

"A binary tree that always puts the extreme at the root."

10 min read Intermediate log N push/pop
01
CORE INTUITION

Always the Max (or Min) at the Top

A binary heap is a complete binary tree where every parent is ≥ (max-heap) or ≤ (min-heap) its children. This property makes the root the maximum or minimum element, retrievable in O(1) time.

Insert (push)

Add to end, bubble up — O(log N)

Extract (pop)

Remove root, sift down — O(log N)

02
VISUAL

Max-Heap in Action

Watch a real insert and extract-max sequence — every comparison and swap shown, one step at a time.

START · step 1 / 38
503040102035
503040102035

Starting max-heap — every parent is already ≥ its children.

03
REPRESENTATION

The Dense Array Structure

Because a heap is a complete binary tree (filled layer-by-layer from left to right), it can be perfectly packed into a flat array without storing child or parent pointers. This layout has superior CPU cache locality because nodes are contiguous in memory.

Child to Parent

Parent(i)

Math.floor((i - 1) / 2)
Parent to Children

Left(i) & Right(i)

Left = 2*i + 1 | Right = 2*i + 2
Array order ≠ sorted order. [50, 30, 40, 10, 20, 35] is a completely valid max-heap — only the root is guaranteed to be the extreme value. Reading left-to-right gives no ordering guarantee beyond "each parent ≥ its two children."
04
COMPLEXITY

The O(N) Heapify Secret

A naive way to build a heap of size N is to start with an empty heap and insert elements one by one. Each insertion takes O(log N), leading to a total time of O(N log N).

However, we can build a heap in O(N) time by using bottom-up heap construction (sifting down from the bottom non-leaf nodes up to the root).

Why is it O(N)?

In a binary tree, half of all nodes are located at the bottom leaf layer (height 0). Leaves already satisfy the heap property, so they require 0 sift-down operations!
The next layer up contains N/4 nodes, which need at most 1 sift-down step. The layer above that has N/8 nodes, requiring at most 2 steps, and so on.

Mathematically, the total sifting work converges:
Work = N/4*(1) + N/8*(2) + N/16*(3) + ... = O(N)
Sifting down is cheaper because the majority of nodes are at the bottom where height is minimal, whereas sifting up requires sifting leaf elements all the way to the top!
05
BLUEPRINTS

Essential Heap Strategies

1. Bottom-Up Heapify (Sift Down)

How it Works

  • Start from index n/2 - 1 (last non-leaf node).
  • Sift down each node to its correct position relative to children.
  • Allows constructing a valid heap in linear O(N) time.
  • Enables efficient in-place heapsort without extra space.
heapify.js
1
function siftDown(arr, n, i) {
2
let largest = i;
3
const left = 2 * i + 1;
4
const right = 2 * i + 2;
5
6
if (left < n && arr[left] > arr[largest]) {
7
largest = left;
8
}
9
if (right < n && arr[right] > arr[largest]) {
10
largest = right;
11
}
12
if (largest !== i) {
13
// Swap parent with the largest child
14
[arr[i], arr[largest]] = [arr[largest], arr[i]];
15
// Recursively sift down the affected sub-tree
16
siftDown(arr, n, largest);
17
}
18
}
19
20
function buildHeap(arr) {
21
const n = arr.length;
22
// Start from the last non-leaf node and sift down
23
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
24
siftDown(arr, n, i);
25
}
26
}

2. Top-K Largest Elements

How it Works

  • Initialize a min-heap.
  • Push each element into the heap one-by-one.
  • If heap size exceeds K, evict the smallest element (root).
  • Takes O(N log K) time and uses only O(K) memory.
topK.js
1
// Assumes a custom MinHeap implementation exists.
2
function topK(nums, k) {
3
const minHeap = new MinHeap(); // Comparator: (a, b) => a - b
4
for (const num of nums) {
5
minHeap.push(num);
6
if (minHeap.size() > k) {
7
minHeap.pop(); // Evict smallest element
8
}
9
}
10
return minHeap.toArray(); // Returns remaining K largest elements
11
}

3. Dynamic Median Tracking (Two Heaps)

How it Works

  • Divide numbers: left lower half in a Max-Heap, right higher half in a Min-Heap.
  • Add number to Max-Heap, then transfer Max-Heap's root to Min-Heap to balance values.
  • If size of Max-Heap is smaller, pull from Min-Heap back to balance sizes.
  • Get median in O(1) time, add elements in O(log N).
medianFinder.js
1
// Assumes MinHeap and MaxHeap helper classes exist.
2
class MedianFinder {
3
constructor() {
4
this.small = new MaxHeap(); // Left half (stores smaller values)
5
this.large = new MinHeap(); // Right half (stores larger values)
6
}
7
8
addNum(num) {
9
this.small.push(num);
10
this.large.push(this.small.pop());
11
12
// Balance heap sizes
13
if (this.small.size() < this.large.size()) {
14
this.small.push(this.large.pop());
15
}
16
}
17
18
findMedian() {
19
if (this.small.size() > this.large.size()) {
20
return this.small.peek();
21
}
22
return (this.small.peek() + this.large.peek()) / 2;
23
}
24
}
06
COMPARISON

When to Use What

Use a Heap

  • Repeatedly need max/min values
  • Finding K-th largest / smallest
  • Dynamic median tracking
  • Merging K sorted streams

Skip the Heap

  • Need fully sorted array (use Sort)
  • Single pass of max/min (use simple scan)
  • Values bounded (use bucket/counting sort)
07
APPLICATIONS

Real-world Heap Systems

1. Dijkstra's Shortest Path Algorithm

Problem: Find the shortest path from a starting node to all other nodes in a weighted graph.
Core Logic: We use a min-heap to keep track of active paths. At each step, we extract the node with the absolute minimum accumulated distance from the heap, which is guaranteed to be finalized, then relax its neighbors.

2. Merge K Sorted Lists

Problem: Merge K sorted linked lists into one single sorted list.
Core Logic: Push the head node of each of the K lists into a min-heap. Pop the minimum node, append it to the result list, and push that node's next node back into the heap. This ensures linear-like merge overhead of O(N log K) instead of quadratic comparisons.

3. CPU Load Balancers & Task Schedulers

Problem: Dispatch tasks based on priority or dynamic response load.
Core Logic: CPU tasks are added to a priority queue (implemented as a binary heap). The scheduler pulls the highest priority task (min-heap based on deadline or priority score) to process next, ensuring key system operations are never blocked.

08
RECOGNITION

How to Spot a Heap Problem

Heaps show up whenever a problem keeps asking for the current extreme (max or min) while the underlying data keeps changing. Watch for phrasing like:

"Kth largest / smallest element"
"Top K frequent elements"
"K closest points to origin"
"Merge K sorted lists / arrays"
"Median of a data stream"
"Reorganize so no two adjacent match"

Classic problems: Kth Largest Element in an Array, Top K Frequent Elements, K Closest Points to Origin, Merge K Sorted Lists, Find Median from Data Stream, Task Scheduler.

09
PITFALLS

Mistakes That Cost Interviews

1. Treating a heap as a sorted array

Only the root is guaranteed to be the extreme value — the rest of the array is not in order. Don't index into the middle expecting sorted output.

2. Assuming JavaScript has a built-in heap

Python has heapq, Java/C++/Go have PriorityQueue / priority_queue / container/heap — JavaScript has none built in. You must bring or hand-roll a Min/MaxHeap class.

3. Flipping the comparator by accident

Python's heapq is always a min-heap — negate values to fake a max-heap. Mixing this up silently returns the smallest element instead of the largest.

4. Wrong heap size for "top K"

Keep a min-heap of size K and evict the smallest once it grows past K — not a max-heap of all N elements, which uses O(N) space and still needs K pops at the end.

10
PRACTICE

Ready to Practice?

Kth Largest ElementMedium
Top K Frequent ElementsMedium
Find Median from Data StreamHard

"A heap is a priority queue — not a sorted list."