A heap is a special binary tree where the parent is always smaller (min-heap) or larger (max-heap) than its children. A priority queue is the abstract concept — “give me the smallest/largest element quickly.” A heap is the data structure that implements it.
In simple language, think of a priority queue like an emergency room. It’s not first-come-first-served. The most urgent patient (highest priority) gets treated first, regardless of when they arrived.
Why Heaps Matter
Without a heap, finding the minimum element in a collection is O(n). With a heap, it’s O(1). Inserting and removing are O(log n). That’s a huge deal when we’re repeatedly asking “what’s the smallest/largest element right now?”
Min-Heap vs Max-Heap
Min-heap: The root is the smallest element. Every parent is smaller than its children.
Max-heap: The root is the largest element. Every parent is larger than its children.
How Heaps Work Under the Hood
A heap is a complete binary tree stored as an array. We don’t need actual node objects or pointers. The tree structure is implicit from the array indices:
- Parent of index
i:Math.floor((i - 1) / 2) - Left child of index
i:2 * i + 1 - Right child of index
i:2 * i + 2
Push (insert): Add to the end of the array, then “bubble up” — swap with parent until the heap property is satisfied.
Pop (extract min/max): Remove the root (index 0), move the last element to the root, then “bubble down” — swap with the smaller (or larger) child until settled.
Both operations are O(log n) because the tree height is log n.
Using Built-in Priority Queues
In interviews, we almost never implement heaps from scratch. We use built-in priority queues.
// JavaScript has NO built-in heap!
// We need to implement one or use a library
// Here's a minimal MinHeap class for interviews
class MinHeap {
constructor() { this.data = []; }
push(val) {
this.data.push(val);
this._bubbleUp(this.data.length - 1);
}
pop() {
const min = this.data[0];
const last = this.data.pop();
if (this.data.length) {
this.data[0] = last;
this._bubbleDown(0);
}
return min;
}
peek() { return this.data[0]; }
size() { return this.data.length; }
_bubbleUp(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.data[parent] <= this.data[i]) break;
[this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
i = parent;
}
}
_bubbleDown(i) {
while (true) {
let smallest = i;
const left = 2 * i + 1, right = 2 * i + 2;
if (left < this.data.length && this.data[left] < this.data[smallest]) smallest = left;
if (right < this.data.length && this.data[right] < this.data[smallest]) smallest = right;
if (smallest === i) break;
[this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]];
i = smallest;
}
}
}# Python -- heapq module (min-heap by default)
import heapq
heap = []
heapq.heappush(heap, 3) # push
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappop(heap) # 1 -- pops smallest
heap[0] # 3 -- peek at smallest
# For max-heap, negate values
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -4)
-heapq.heappop(max_heap) # 4 -- largest value// Java -- PriorityQueue (min-heap by default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(3); // push
minHeap.offer(1);
minHeap.offer(4);
minHeap.poll(); // 1 -- pops smallest
minHeap.peek(); // 3 -- peek at smallest
// For max-heap, use reverse comparator
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(4);
maxHeap.poll(); // 4 -- pops largestPython note: heapq only supports min-heaps. The standard trick for a max-heap is to negate values: push -val, pop and negate back. It’s ugly but it works.
JavaScript note: There’s no built-in heap in JavaScript. In interviews, either write a quick MinHeap class (like above) or mention that we’d use one.
Top K Frequent Elements
Given an array, find the K most frequent elements. This is a classic heap problem.
Strategy: Count frequencies with a hash map, then use a min-heap of size K. We push each element and pop when the heap exceeds size K. At the end, everything left in the heap is a top-K element.
Why a min-heap and not a max-heap? Because we want to evict the least frequent element when the heap is full. The min-heap keeps the smallest frequency at the top, ready to be kicked out.
// Top K frequent elements -- O(n log k)
function topKFrequent(nums, k) {
// step 1: count frequencies
const freq = new Map();
for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
// step 2: use a min-heap of size k
// (using our MinHeap class storing [frequency, number])
const heap = new MinHeap(); // compare by first element (freq)
for (const [num, count] of freq) {
heap.push([count, num]);
if (heap.size() > k) heap.pop(); // evict least frequent
}
// step 3: extract results
const result = [];
while (heap.size()) result.push(heap.pop()[1]);
return result;
}# Top K frequent elements -- O(n log k)
import heapq
from collections import Counter
def top_k_frequent(nums, k):
# step 1: count frequencies
freq = Counter(nums)
# step 2: use a min-heap of size k
# heapq compares tuples by first element (count)
heap = []
for num, count in freq.items():
heapq.heappush(heap, (count, num))
if len(heap) > k:
heapq.heappop(heap) # evict least frequent
# step 3: extract results
return [num for count, num in heap]// Top K frequent elements -- O(n log k)
static int[] topKFrequent(int[] nums, int k) {
// step 1: count frequencies
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
// step 2: use a min-heap of size k
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (var entry : freq.entrySet()) {
heap.offer(new int[]{entry.getValue(), entry.getKey()});
if (heap.size() > k) heap.poll(); // evict least frequent
}
// step 3: extract results
int[] result = new int[k];
for (int i = 0; i < k; i++) result[i] = heap.poll()[1];
return result;
}Merge K Sorted Lists (Concept)
Given K sorted linked lists, merge them into one sorted list. Brute force: merge two at a time, K-1 times. That works but is O(N * K) where N is the total number of nodes.
With a min-heap: push the first node of each list into the heap. Pop the smallest, add it to the result, and push that node’s next into the heap. We always have at most K elements in the heap, so each push/pop is O(log K).
Total time: O(N log K) — much better when K is large.
// Merge K sorted lists -- O(N log K)
function mergeKLists(lists) {
const heap = new MinHeap(); // stores [val, listIndex, node]
// push first node from each list
for (let i = 0; i < lists.length; i++) {
if (lists[i]) heap.push([lists[i].val, i, lists[i]]);
}
const dummy = new ListNode(0);
let tail = dummy;
while (heap.size()) {
const [val, idx, node] = heap.pop(); // get smallest
tail.next = node;
tail = tail.next;
if (node.next) heap.push([node.next.val, idx, node.next]);
}
return dummy.next;
}# Merge K sorted lists -- O(N log K)
import heapq
def merge_k_lists(lists):
heap = []
# push first node from each list
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst.val, i, lst))
dummy = ListNode(0)
tail = dummy
while heap:
val, idx, node = heapq.heappop(heap) # get smallest
tail.next = node
tail = tail.next
if node.next:
heapq.heappush(heap, (node.next.val, idx, node.next))
return dummy.next// Merge K sorted lists -- O(N log K)
static ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>(
(a, b) -> a.val - b.val
);
for (ListNode list : lists) {
if (list != null) heap.offer(list);
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!heap.isEmpty()) {
ListNode node = heap.poll(); // get smallest
tail.next = node;
tail = tail.next;
if (node.next != null) heap.offer(node.next);
}
return dummy.next;
}Time Complexities
| Operation | Time |
|---|---|
| peek (get min/max) | O(1) |
| push (insert) | O(log n) |
| pop (extract min/max) | O(log n) |
| heapify (build heap from array) | O(n) |
| search | O(n) — heaps aren’t designed for search |
The O(n) heapify is surprising — building a heap from an unsorted array is O(n), not O(n log n). We won’t prove it here, but it’s a useful fact for interviews.
When to Think Heap
- “Find the K largest/smallest” — classic heap signal
- “Merge K sorted things” — min-heap to track the smallest across K sources
- “Continuously find min/max” in a stream of data
- “Median of a stream” — use two heaps (max-heap for lower half, min-heap for upper half)
- “Schedule tasks by priority” — that’s literally a priority queue
If sorting the entire collection seems wasteful because we only need the top K elements, a heap is probably the answer. Sorting is O(n log n); a heap approach for top K is O(n log k) — and when k is small, that’s much faster.