Classic greedy algorithms worth knowing

A handful of greedy algorithms are famous precisely because their correctness is provable. Knowing them by name and by strategy is the expected baseline.

Huffman coding

Build an optimal prefix-free code: repeatedly merge the two least frequent symbols into one node, using a min-heap.

// Frequencies → a binary tree where common symbols sit near the root.
// The greedy choice: the two rarest symbols should be deepest, so merge them first.

The exchange argument works: in any optimal tree, the two rarest symbols can be moved to the deepest sibling pair without increasing the total cost. This is the basis of DEFLATE, and therefore of gzip, PNG and ZIP.

Kruskal's minimum spanning tree

Sort every edge by weight and add it if it does not create a cycle, using a union-find structure to test that in near-constant time.

// Sort edges ascending; union(a, b) returns false if they are already connected.
// O(E log E), dominated by the sort.

Union-find (disjoint set union) is worth learning alongside it: find with path compression and union by rank give effectively O(1) amortised operations, and it independently solves connectivity, cycle detection and account-merging questions.

Prim's minimum spanning tree

Grow one tree outward, always taking the cheapest edge leaving it — a min-heap over frontier edges, structurally the same loop as Dijkstra. O(E log V), and preferable to Kruskal on dense graphs.

Fractional knapsack

Take items by value-to-weight ratio, splitting the last one. Optimal because a fraction can always fill the remaining capacity exactly.

The 0/1 knapsack, where items cannot be split, is not solvable greedily — that single difference is the standard illustration of where greedy ends and dynamic programming begins.

Activity selection and job sequencing

Earliest finishing time first, as in the interval lesson. With deadlines and profits, sort by profit descending and schedule each job as late as its deadline allows, which keeps early slots free for what follows.

The pattern behind all of them

Every one sorts by a carefully chosen key, then commits. When you meet a new optimisation problem, ask: is there a single ordering that makes the first choice obviously safe? If yes, you have a greedy algorithm and an exchange argument to write. If no, the next chapter is where you should be.