Greedy Algorithms Powered by a Heap

August 2026 · 23 min read

A greedy algorithm repeatedly makes a locally optimal choice. When “locally optimal” means “the smallest” or “the largest” of a set that keeps changing, a heap is the machinery that makes the choice cheap. This post covers the classics — Huffman coding, Dijkstra, Prim, and the regret-based greedy that lets you undo an earlier decision.

Huffman Coding

The purest example. Given symbol frequencies, build the prefix code minimising total encoded length. The greedy rule is one line: repeatedly merge the two least frequent nodes.

#include <queue>
#include <vector>
#include <string>
#include <unordered_map>

struct Node {
    int   freq;
    char  symbol;
    Node* left;
    Node* right;
};

struct ByFreq {
    bool operator()(const Node* a, const Node* b) const { return a->freq > b->freq; }  // min-heap
};

Node* buildHuffman(const std::unordered_map<char,int>& freq) {
    std::priority_queue<Node*, std::vector<Node*>, ByFreq> heap;
    for (const auto& kv : freq)
        heap.push(new Node{kv.second, kv.first, nullptr, nullptr});

    while (heap.size() > 1) {
        Node* a = heap.top(); heap.pop();
        Node* b = heap.top(); heap.pop();
        heap.push(new Node{a->freq + b->freq, '\0', a, b});   // internal node
    }
    return heap.empty() ? nullptr : heap.top();
}

Why merging the two smallest is optimal. In an optimal prefix code the two least frequent symbols must be siblings at the deepest level. If they were not, you could swap one with a deeper node of higher frequency and strictly reduce the total cost — so no code that separates them can be optimal. Merging them and recursing on the reduced problem therefore preserves optimality by induction. This exchange argument is the standard template for proving greedy correctness.

Cost: O(n log n) for n symbols. If the frequencies arrive already sorted, two FIFO queues replace the heap and it drops to O(n) — a neat trick worth knowing, since merged nodes are themselves generated in non-decreasing order.

Dijkstra's Shortest Path

The most important heap application in practice. Repeatedly settle the unvisited vertex with the smallest tentative distance — again a minimum query over a changing set.

#include <queue>
#include <vector>
#include <limits>

std::vector<long long> dijkstra(int n,
        const std::vector<std::vector<std::pair<int,int>>>& adj, int src) {
    const long long INF = std::numeric_limits<long long>::max();
    std::vector<long long> dist(n, INF);

    using State = std::pair<long long,int>;                 // (distance, vertex)
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;                          // stale entry: skip it

        for (const auto& [v, w] : adj[u]) {
            long long nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push({nd, v});                           // lazy decrease-key
            }
        }
    }
    return dist;
}

The line if (d > dist[u]) continue; is lazy deletion, and it is the single most important idiom here. Because std::priority_queue cannot lower an existing element's key, we push a new entry with the improved distance and leave the old one to rot. When a stale entry surfaces, its stored distance exceeds the best known, so we discard it. Omitting this check does not produce wrong answers — distances are already final — but it re-relaxes every outgoing edge and can badly degrade performance on dense graphs.

Note that log E <= log(V2) = 2 log V, so the lazy version's extra entries cost only a constant factor. That is why almost nobody bothers with an indexed heap in practice.

Prim's Minimum Spanning Tree

Structurally almost identical to Dijkstra; only the key changes. Dijkstra keys on total distance from the source; Prim keys on the weight of the single edge connecting a vertex to the tree built so far.

long long prim(int n, const std::vector<std::vector<std::pair<int,int>>>& adj) {
    std::vector<bool> inTree(n, false);
    using Edge = std::pair<int,int>;                        // (weight, vertex)
    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;

    pq.push({0, 0});
    long long total = 0;
    int taken = 0;

    while (!pq.empty() && taken < n) {
        auto [w, u] = pq.top();
        pq.pop();
        if (inTree[u]) continue;                            // stale entry

        inTree[u] = true;
        total += w;
        ++taken;

        for (const auto& [v, wt] : adj[u])
            if (!inTree[v]) pq.push({wt, v});
    }
    return taken == n ? total : -1;                         // -1 if the graph is disconnected
}

That one-word difference in the key — cumulative versus incremental — is the entire distinction between shortest paths and minimum spanning trees. Worth internalising, because it makes both algorithms one thing to remember instead of two.

Regret Greedy: Undoing a Choice

The most interesting pattern in this post, and the one that separates a heap from a simple sort. Some problems allow you to take an item now and revoke it later if something better appears. The heap holds your reversible commitments.

Course Schedule III: each course has a duration and a deadline; maximise the number of courses taken. Sort by deadline and take everything greedily — but when a course does not fit, check whether swapping out the longest course taken so far makes room:

int scheduleCourse(std::vector<std::vector<int>>& courses) {
    std::sort(courses.begin(), courses.end(),
              [](const auto& a, const auto& b) { return a[1] < b[1]; });   // by deadline

    std::priority_queue<int> taken;                         // MAX-heap of durations taken
    long long time = 0;

    for (const auto& c : courses) {
        int dur = c[0], due = c[1];
        if (time + dur <= due) {                            // fits: take it
            taken.push(dur);
            time += dur;
        } else if (!taken.empty() && taken.top() > dur) {   // regret: swap out the longest
            time += dur - taken.top();
            taken.pop();
            taken.push(dur);
        }
    }
    return (int)taken.size();
}

The count never decreases — a swap keeps it identical while strictly reducing elapsed time, which can only help future courses fit. A max-heap makes “the longest thing I have committed to” an O(1) lookup, which is exactly the regret candidate. Sorting alone cannot do this, because the decision to revoke depends on state that only exists mid-scan.

The same shape solves IPO / Maximum Capital, Maximum Performance of a Team (a min-heap of the weakest kept members, evicted as the efficiency threshold falls), and several “maximum profit with constraints” problems.

Recognising the Pattern

Reach for a heap-backed greedy when all three hold:

1. The choice at each step is an extreme — smallest, largest, cheapest, soonest.
2. The candidate set changes as you go — items are added or consumed. If it were fixed, a sort would do.
3. The greedy choice is provably safe, usually by an exchange argument: assume an optimal solution differs from the greedy pick, then swap it in without making things worse.

Condition 2 is the discriminator. Sorting handles a static candidate set; a heap is what you need when the set is alive.

Practice

• Network Delay Time medium — Dijkstra, essentially verbatim.
• Path with Minimum Effort medium — Dijkstra with a max-edge key instead of a sum.
• Min Cost to Connect All Points medium — Prim on a complete graph.
• Course Schedule III hard — the regret pattern above.
• Minimum Cost to Hire K Workers hard — sort by ratio, heap of the k smallest quality values.
• Last Stone Weight easy — a gentle warm-up on repeated extraction.
• Minimum Number of Refueling Stops hard — regret greedy over fuel already passed.