Heap Problems on LeetCode: C++ Solutions with Explanations

2025-08-11

Heaps show up all over LeetCode. If you know how to use std::priority_queue with custom comparators, you can solve a large set of problems quickly. This guide gives you clean C++ templates, explains why they work, and points out mistakes that cost time in interviews.

Quick primer on heaps in C++

Default priority_queue<int> is a max heap.
For a min heap, use priority_queue<int, vector<int>, greater<int>> pq;
Custom ordering uses a comparator functor or lambda.
Operations: push and pop are O(log n), top is O(1).

#include <queue>
#include <vector>
#include <functional>
using namespace std;

// max heap
priority_queue<int> mx;

// min heap
priority_queue<int, vector<int>, greater<int>> mn;

Pattern 1: Keep k best items with a min heap

Use when: you need the k largest values or k strongest candidates.

Idea: keep a min heap of size k. If the next value is better than top, pop then push.

Example: K largest elements.

#include <vector>
#include <queue>
using namespace std;

vector<int> kLargest(const vector<int>& a, int k) {
    priority_queue<int, vector<int>, greater<int>> pq; // min heap
    for (int x : a) {
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();
    }
    vector<int> out;
    while (!pq.empty()) { out.push_back(pq.top()); pq.pop(); }
    return out; // not sorted by default
}
// Time O(n log k), Space O(k)

Why it works: the smallest of your current top k sits at top. Anything worse gets ignored.

Pattern 2: Kth largest in an array

Identical to Pattern 1, but return pq.top() at the end.

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

Pattern 3: Top K Frequent Elements

Use when: ranking by frequency.

Idea: count in a hash map, then push pairs into a min heap keyed by frequency.

#include <unordered_map>
#include <utility>

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> freq;
    for (int x : nums) freq[x]++;

    using P = pair<int,int>; // {freq, value}
    auto cmp = [](const P& a, const P& b) { return a.first > b.first; }; // min heap by freq
    priority_queue<P, vector<P>, decltype(cmp)> pq(cmp);

    for (auto& [val, f] : freq) {
        pq.push({f, val});
        if ((int)pq.size() > k) pq.pop();
    }
    vector<int> res;
    while (!pq.empty()) { res.push_back(pq.top().second); pq.pop(); }
    return res;
}
// Time O(n log k), Space O(n)

Pattern 4: Merge K Sorted Lists

Use when: merging many sorted streams.

Idea: min heap stores the current smallest head from each list.

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

#include <queue>

ListNode* mergeKLists(vector<ListNode*>& lists) {
    struct Item { int val; ListNode* node; };
    auto cmp = [](const Item& a, const Item& b) { return a.val > b.val; }; // min heap
    priority_queue<Item, vector<Item>, decltype(cmp)> pq(cmp);

    for (auto* p : lists) if (p) pq.push({p->val, p});

    ListNode dummy(0), *tail = &dummy;
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        tail->next = cur.node; tail = tail->next;
        if (cur.node->next) pq.push({cur.node->next->val, cur.node->next});
    }
    return dummy.next;
}
// Time O(N log k), N total nodes

Pattern 5: K Closest Points to Origin

Use when: ordering by a custom score.

Idea: keep a max heap of size k keyed by distance. Pop when heap grows beyond k.

#include <cmath>

vector<vector<int>> kClosest(vector<vector<int>>& pts, int k) {
    auto dist2 = [](const vector<int>& p){ return 1LL*p[0]*p[0] + 1LL*p[1]*p[1]; };

    using P = pair<long long,int>; // {dist2, index}
    auto cmp = [](const P& a, const P& b){ return a.first < b.first; }; // max heap by dist
    priority_queue<P, vector<P>, decltype(cmp)> pq(cmp);

    for (int i = 0; i < (int)pts.size(); i++) {
        pq.push({dist2(pts[i]), i});
        if ((int)pq.size() > k) pq.pop();
    }
    vector<vector<int>> res;
    while (!pq.empty()) { res.push_back(pts[pq.top().second]); pq.pop(); }
    return res;
}
// Time O(n log k)

Pattern 6: Stream median with two heaps

Use when: data arrives one by one and you need the median anytime.

Idea: max heap for lower half, min heap for upper half. Keep sizes balanced.

class MedianFinder {
    priority_queue<int> lo; // max heap
    priority_queue<int, vector<int>, greater<int>> hi; // min heap
public:
    void addNum(int num) {
        if (lo.empty() || num <= lo.top()) lo.push(num);
        else hi.push(num);

        if (lo.size() > hi.size() + 1) { hi.push(lo.top()); lo.pop(); }
        else if (hi.size() > lo.size()) { lo.push(hi.top()); hi.pop(); }
    }
    double findMedian() const {
        if (lo.size() == hi.size()) return (lo.top() + hi.top()) / 2.0;
        return lo.top();
    }
};

Pattern 7: Sliding Window Median

Use when: windowed statistics with order dependence.

Idea: two multisets or two heaps plus lazy deletion. Heaps work with a hash map that tracks stale entries.

Sketch:

// O(n log n) approach uses two multisets for simplicity
#include <set>

vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    multiset<int> lo, hi; // lo holds the smaller half (max), hi holds larger half (min)
    auto rebalance = [&]() {
        while (lo.size() > hi.size() + (k % 2)) {
            hi.insert(*lo.rbegin());
            lo.erase(prev(lo.end()));
        }
        while (lo.size() < hi.size()) {
            lo.insert(*hi.begin());
            hi.erase(hi.begin());
        }
    };

    vector<double> res;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (lo.empty() || nums[i] <= *lo.rbegin()) lo.insert(nums[i]);
        else hi.insert(nums[i]);
        rebalance();

        if (i >= k) {
            // remove nums[i - k]
            if (nums[i - k] <= *lo.rbegin()) {
                auto it = lo.find(nums[i - k]);
                lo.erase(it);
            } else {
                auto it = hi.find(nums[i - k]);
                hi.erase(it);
            }
            rebalance();
        }
        if (i >= k - 1) {
            if (k % 2) res.push_back(*lo.rbegin());
            else res.push_back(((double)*lo.rbegin() + *hi.begin()) / 2.0);
        }
    }
    return res;
}

This version uses multiset for clear removals. If you need strict heaps only, add lazy deletion maps.

Pattern 8: Meeting Rooms II

Use when: find the minimum number of resources to cover intervals.

Idea: sort by start time, keep a min heap of end times. If the earliest ending room is free, reuse it.

#include <algorithm>

int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end()); // sort by start
    priority_queue<int, vector<int>, greater<int>> ends; // min heap of end times
    for (auto& it : intervals) {
        if (!ends.empty() && ends.top() <= it[0]) ends.pop(); // reuse room
        ends.push(it[1]);
    }
    return (int)ends.size();
}

Pattern 9: Reorganize String and Task Scheduling

Use when: always pick the most frequent remaining item while respecting cooldown or spacing.

Idea: max heap by remaining count.

Sketch for reorganize string:

#include <string>
#include <unordered_map>

string reorganizeString(const string& s) {
    unordered_map<char,int> cnt;
    for (char c : s) cnt[c]++;
    using P = pair<int,char>;
    auto cmp = [](const P& a, const P& b){ return a.first < b.first; }; // max heap by count
    priority_queue<P, vector<P>, decltype(cmp)> pq(cmp);
    for (auto& [c, f] : cnt) pq.push({f, c});

    string out;
    P hold = {0, '#'};
    while (!pq.empty()) {
        auto [f, c] = pq.top(); pq.pop();
        out.push_back(c);
        if (hold.first > 0) pq.push(hold);
        hold = {f - 1, c};
    }
    if ((int)out.size() != (int)s.size()) return ""; // impossible
    return out;
}

Common pitfalls

Using a max heap where you meant min heap. Remember the default is max.
Comparator direction wrong. For min heap use greater<T> or a custom return a > b style.
Storing heavy structs by value without move or indexes. For performance, store indices or pointers when safe.
Forgetting to limit heap size to k leads to O(n log n) instead of O(n log k).
For stream median and sliding window median, not balancing both halves after every update.

When to choose heaps over sorting

You only need the best k items, not a full ordering.
You process a stream and must answer online.
You need to repeatedly pick the current best candidate as state changes.

If you need a full global order once, sorting is often simpler and just as fast.

Interview checklist you can say out loud

What is the score or priority that decides which item is better
Can I keep only k items and ignore the rest
Is this a min heap or a max heap problem
What is the exact comparator and what does top() represent
What is the time complexity in terms of n and k
Any reason to prefer indices or pointers to avoid copies

Practice set

Kth Largest Element in an Array
Top K Frequent Elements
K Closest Points to Origin
Merge K Sorted Lists
Find Median from Data Stream
Sliding Window Median
Meeting Rooms II
Reorganize String
Task Scheduler

Work through these and heaps will start to feel like a natural tool.

If you want a helper while practicing that can show a clean heap solution and a short explanation when you are stuck, you can use an overlay that stays off your screen share and responds to a hotkey. It lets you keep momentum without derailing the session.

Try StealthCoder when you want a concise outline and working code to study during practice: https://stealthcoder.app