DSA · Lesson 9 of 17

Heaps & Priority Queues

⏱ 14 min🎬 Interactive visualizer💻 Python · Java · C++ · JavaScript🧩 4 practice problems

A heap always hands you the smallest (or largest) item in O(log n). The tool for top-k, k-way merge, scheduling and Dijkstra.

The idea

A binary heap is a complete binary tree stored in an array where every parent is ≤ its children (a min-heap). The minimum is always at index 0. Children of index i are 2i + 1 and 2i + 2; the parent is (i − 1) / 2.

push: append at the end, then sift up while smaller than the parent: O(log n)
pop: take the root, move the last element to the root, then sift down: O(log n)
peek: O(1). Building a heap from n items: O(n).

Patterns

Top-k / k-th largest: keep a min-heap of size k; whenever it exceeds k, pop. The root is the k-th largest. O(n log k).
K-way merge: push the head of each sorted list and repeatedly pop the smallest (Merge k Sorted Lists, smallest range).
Two heaps: a max-heap for the lower half and a min-heap for the upper half give the running median.
Scheduling / greedy: always process the most urgent item (meeting rooms, task scheduler, CPU scheduling).
Shortest paths: Dijkstra pops the closest unfinished node.

Language notes

Language	Min-heap	Max-heap
Python	`heapq` (min only)	push `-x`
Java	`new PriorityQueue<>()`	`new PriorityQueue<>(Collections.reverseOrder())`
C++	`priority_queue<int, vector<int>, greater<int>>`	`priority_queue<int>` (max by default!)
JavaScript	none built in: write a small heap class (included in our solutions)	same class, reversed comparator

Code template

import heapq

def k_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)      # evict the smallest
    return sorted(heap, reverse=True)

# max-heap trick: store negatives
mx = []
heapq.heappush(mx, -5); largest = -mx[0]

List<Integer> kLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();        // min-heap
    for (int x : nums) { heap.offer(x); if (heap.size() > k) heap.poll(); }
    List<Integer> res = new ArrayList<>(heap);
    res.sort(Collections.reverseOrder());
    return res;
}

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

vector<int> kLargest(const vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> heap;       // min-heap
    for (int x : nums) { heap.push(x); if ((int)heap.size() > k) heap.pop(); }
    vector<int> res;
    while (!heap.empty()) { res.push_back(heap.top()); heap.pop(); }
    reverse(res.begin(), res.end());
    return res;
}

priority_queue<int> maxHeap;   // max-heap by default

class MinHeap {
  constructor(less = (a, b) => a < b) { this.a = []; this.less = less; }
  get size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {
    const a = this.a; a.push(x); let i = a.length - 1;
    while (i > 0) { const p = (i - 1) >> 1; if (!this.less(a[i], a[p])) break; [a[i], a[p]] = [a[p], a[i]]; i = p; }
  }
  pop() {
    const a = this.a, top = a[0], last = a.pop();
    if (a.length) {
      a[0] = last; let i = 0;
      for (;;) {
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

Practise this pattern (4 problems)

Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.

#	Problem	Difficulty
41	Last Stone Weight	Easy
42	Kth Largest Element in an Array	Medium
43	K Closest Points to Origin	Medium
44	Merge k Sorted Lists	Hard

Common mistakes

C++ priority_queue is a max-heap by default.
Python heapq with tuples compares the second element on ties: add an index as a tie-breaker so objects are never compared.
Using a heap where sorting once would do, or sorting repeatedly where a heap is needed.

Check yourself: to find the 3 largest of a million numbers, min-heap or max-heap?

A min-heap of size 3. Its root is the smallest of the current top 3, the one to evict when something bigger arrives.

🧩 All DSA problems 🎬 Algorithm visualizer 🎓 Certificates

Created by Ajeetkumar