roadmap/Heap / Priority Queue

Topic 8 / 16

Heap / Priority Queue

MediumNon-Linear~3 days
Moderate
progress0 / 10 solved

O(log n) access to the min or max element. Essential for top-K and scheduling problems.

Prerequisites
← Trees
Concept

A heap is a complete binary tree satisfying the heap property: every parent is smaller (min-heap) or larger (max-heap) than its children. In JS/Python, use a priority queue library. Key operations: push O(log n), pop O(log n), peek O(1). Use a min-heap for 'Kth largest' (keep K elements, the min is the Kth largest).

When to use this pattern
  • ◆Kth largest or Kth smallest element
  • ◆Median of a data stream
  • ◆Merge K sorted lists
  • ◆Task scheduling with priorities
  • ◆Dijkstra's shortest path
Common patterns
Top-K elements
Min-heap of size K. Pop when size exceeds K. Top is the Kth largest.
Two heaps (median)
Max-heap for lower half, min-heap for upper half. Balance sizes.
K-way merge
Push the first element of each list; pop and push next from that list.
Greedy scheduling
Always pick the task with highest priority from the heap.
Brute force → optimal thinking
Brute force
Sort the array and pick the Kth element → O(n log n).
Observation
We don't need to sort everything — we only need the top K.
Optimization
Maintain a min-heap of size K. For each new element, if it's larger than the heap's min, pop min and push the new element.
Final complexity
O(n log K) — far better than O(n log n) when K << n.
Quick Recall Check

To find the Kth largest element efficiently, which heap do you use and what size?

What is the time complexity of a heap push or pop?

In the two-heaps pattern for finding a median, what invariant must hold?

Am I ready to move on?

Check each question you can answer confidently before moving to the next topic.

←
previous
Trees
next
Backtracking
→
Progress is saved on this device