Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Heaps and Priority Queue

A heap is a complete binary tree where every parent is smaller than its children (min-heap) or larger than them (max-heap). So the minimum (or maximum) is always at the root.

A priority queue is the abstract idea — "always give me the most important item" — and a heap is how it is usually built.

Stored in an array

A complete tree fits in an array with no pointers. For index i (0-based):

min-heap:        1
               /   \
              3     5        array: [1, 3, 5, 7, 4, 8]
             / \   /
            7   4 8

Operations

Operation How Time
Peek min/max a[0] O(1)
Insert add at the end, sift up while smaller than the parent O(log n)
Remove min/max move the last element to the root, sift down O(log n)
Build heap from n items sift down from the last parent to the root O(n)
void siftDown(vector<int>& h, int i) {           // min-heap
    int n = h.size();
    while (true) {
        int smallest = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && h[l] < h[smallest]) smallest = l;
        if (r < n && h[r] < h[smallest]) smallest = r;
        if (smallest == i) break;
        swap(h[i], h[smallest]);
        i = smallest;
    }
}

C++ priority_queue

priority_queue<int> maxHeap;                              // largest on top
priority_queue<int, vector<int>, greater<int>> minHeap;   // smallest on top

maxHeap.push(5); maxHeap.push(9);
cout << maxHeap.top();   // 9
maxHeap.pop();

// pairs: ordered by first, then second
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;   // (distance, node) for Dijkstra

Java: PriorityQueue<Integer> is a min-heap by default; new PriorityQueue<>(Collections.reverseOrder()) for max. Python: heapq (min-heap; push -x for max).

Pattern 1: top K elements

K largest elements — keep a min-heap of size K; if it grows past K, pop the smallest. What remains are the K largest. Time O(n log K), better than sorting when K is small.

int kthLargest(vector<int>& a, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : a) {
        pq.push(x);
        if (pq.size() > k) pq.pop();
    }
    return pq.top();
}

Same idea: top K frequent elements, K closest points to the origin.

Pattern 2: merge K sorted lists/arrays

Push the first element of each list; pop the smallest, push its next. O(N log K) for N total elements.

Pattern 3: running median

Two heaps: a max-heap for the smaller half and a min-heap for the larger half, kept balanced (sizes differ by ≤ 1). The median is at the top(s). Each insert O(log n).

Pattern 4: greedy scheduling

Heap sort

Build a max-heap, then repeatedly swap the root with the last element and sift down. O(n log n), O(1) space, not stable.

Classic problems

Problem Heap
Kth largest element min-heap of size K
Top K frequent elements count + min-heap
K closest points to origin max-heap of size K
Merge K sorted lists min-heap
Find median from data stream two heaps
Last stone weight max-heap
Minimum cost to connect ropes min-heap
Task scheduler max-heap of counts

Practise in the Heap & Priority Queue section.

Interview one-liners

More DSA notes