Heaps

Priority queues answer 'what's the smallest or largest right now?'. Use bounded heaps for top-k, dual heaps for running medians, and lazy deletion for sliding-window extrema.

12 problems 1 Easy 6 Medium 5 Hard

A heap is a priority queue supporting O(log n) push and O(log n) pop of the extreme element. Common patterns: bounded heap of size k for top-k queries (min-heap → top-k largest, max-heap → top-k smallest); dual heaps (one min, one max) for running medians; lazy deletion for sliding-window extrema where direct removal is expensive.

The heap encodes 'priority' — the right comparator turns ad-hoc scheduling into a one-line decision.

When to reach for this pattern

Need the smallest or largest of the current set, repeatedly
Top-k or kth smallest across a stream or multiple sources
Running median / streaming quantile
Scheduling: take the cheapest / most-urgent task next

Canonical template

priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

// top-k largest via bounded min-heap of size k
for (int x : nums) {
    minHeap.push(x);
    if ((int)minHeap.size() > k) minHeap.pop();
}
// minHeap.top() is the kth-largest.

C++ · adapt the names and types to your problem.

Common pitfalls

Forgetting greater for min-heap (default is max-heap in C++)
Bounding by <= k vs < k — off-by-one on the kept set's size
Custom comparator returns true when the *first* argument has *lower* priority — opposite of intuition
Sliding-window heap needs lazy deletion: skip tops whose indices are stale

Related patterns

K-way Merge Top K Elements Greedy Techniques

Heaps

When to reach for this pattern

Canonical template

Common pitfalls

Related patterns

Problems (12)

Keyboard shortcuts