A log window has five event types: OK, WARN, INFO, ERROR, FATAL. Thirty lines. Product wants them smaller on the wire. The intern assigns three bits each — ceil(log2(5)) — so every OK costs as much as FATAL. OK is twelve of the thirty. That is the waste: a fixed-width alphabet tax on a skewed table.
Huffman builds a prefix-free code from frequencies: merge the two lightest nodes until one tree remains, then read 0/1 down the paths. Frequent symbols sit near the root. Rare ones take the long walk. Concatenated bits decode without a separator because no code is a prefix of another.
This post is that tree. Families and the catalog live on the Algorithms Roadmap. The merge order is a min-heap (Heaps); the JDK type is PriorityQueue. It is not gzip, not zip, and not LZ77 — those are a later sliding-window story. It is not a reason to open knapsack, coin change, or LCS.
The job is a prefix-free table, not equal-width bits
A prefix-free (instantaneous) code: no symbol’s bit string is a prefix of another’s. OK = 0 and WARN = 10 can sit on the same wire. OK = 0 and WARN = 00 cannot — the decoder that just read 0 does not know whether to stop.
Fixed-width sidesteps the clash by making every code the same length. It also refuses to spend fewer bits on the symbol that dominates the log. Huffman keeps the prefix-free contract and lets lengths differ.
You need a frequency table first. Count, then code. One pass over the window for counts, then a heap of size alphabet, not of size stream. The thirty lines are the payload; the five types are the nodes.
Note: Unused symbols stay out of the map. A zero-count leaf still consumes a code. Omit it.
Merge the two lightest, again
Each symbol starts as a leaf weighted by its count. A min-heap holds the current forest. While more than one node remains:
- Poll the two lightest nodes
aandb. - Make a parent of weight
a.freq + b.freq, childrenaandb. - Offer the parent back.
The last node is the root. Walk left = 0, right = 1 (the opposite labeling is the same algorithm). Each leaf path is that symbol’s code.
The greedy move is always “combine the two cheapest remaining trees.” You do not enumerate every prefix-free table. You do not sort the forest after every merge — that is the heap’s job, O(log n) per poll and offer.
One symbol and the loop never runs: the root is the leaf, the path is empty. Assign "0" so a stream of repeats still has bits. Empty alphabet: throw. There is no code.
A walk: five event types
Counts from the window. Total 30. Heap order is lightest first.
OK 12 WARN 7 INFO 6 ERROR 3 FATAL 2
poll FATAL 2, ERROR 3 → N1 5 heap: N1 5, INFO 6, WARN 7, OK 12
poll N1 5, INFO 6 → N2 11 heap: WARN 7, N2 11, OK 12
poll WARN 7, N2 11 → N3 18 heap: OK 12, N3 18
poll OK 12, N3 18 → Root 30
Root 30
/ \
OK 12 N3 18
/ \
WARN 7 N2 11
/ \
N1 5 INFO 6
/ \
FATAL 2 ERROR 3
left=0, right=1:
OK 0
WARN 10
INFO 111
FATAL 1100
ERROR 1101
weighted bits: 12·1 + 7·2 + 6·3 + 2·4 + 3·4 = 64
average: 64/30 ≈ 2.13 bits/symbol (fixed-width was 3)No code is a prefix of another: 0, 10, 111, 1100, 1101. Decode walks from the root until a leaf. Bits 10 are WARN in two steps; you never wait for a delimiter.
Ties in frequency produce different trees with the same weighted path length. PriorityQueue does not promise a stable sibling order. Tests that assert exact bit strings should break ties on purpose (symbol name, insertion id). Tests that assert average length should not.
Why greedy is the right bill here
The cost you minimize is average code length under this frequency table — equivalently, the weighted external path length of a full binary tree whose leaves are the symbols. The constraint is prefix-free. That is a smaller job than “smallest file on disk.”
Greedy-choice holds: there is an optimal tree in which the two rarest symbols are siblings, as deep as the tree goes. Using extra bits on them hurts the average least. Once they share a parent, that parent is a super-symbol of frequency a + b, and the leftover alphabet is the same problem one symbol smaller. Optimal substructure: an optimal tree for the reduced alphabet plus that one merge is optimal for the original.
Local “merge lightest” is global min average length for prefix-free codes on a known independent-symbol table. That is the hub’s greedy-vs-DP line, not a license to greedy-pick knapsack items. Integer bit lengths cannot beat Shannon entropy; they can match it on lucky tables and sit a fraction above it on others. Huffman does not emit fractional bits. Arithmetic coding is a different procedure.
Note: The table is assumed static and known. Adaptive Huffman updates as symbols arrive. This post does not walk it. Two-pass (count, then encode) is the contract above.
Not DEFLATE, not zip, not LZ77
Huffman is the prefix-code builder. gzip, zip, and PNG’s DEFLATE path are not “run Huffman on the raw bytes.” They find repeated substrings with a sliding window (LZ77), then Huffman-code the tokens (literals, lengths, distances). The window is the compressor. Huffman is the entropy stage after it.
Do not ship this tree and call the file gzip. Do not treat a Huffman lab as a zip implementation. LZ77 and DEFLATE own the sliding-window compressor and the pairing. Out of scope here: writing gzip, bit-packing a canonical bitstream, or a DEFLATE block layout.
Canonical Huffman (the lengths Huffman found, then a standardized assignment of the bit strings) is what wire formats want so two encoders agree. That packing is a last step this post does not own. Same lengths, different labels.
Java: a heap of nodes, then a walk
No java.util.Huffman. Leaves carry the symbol; internal nodes carry null and a sum. Comparable is frequency only — the PriorityQueue post owns comparator vs natural order; this sketch uses compareTo.
static final class Node implements Comparable<Node> {
final String sym; // null = internal
final int freq;
final Node left, right;
Node(String sym, int freq, Node left, Node right) {
this.sym = sym;
this.freq = freq;
this.left = left;
this.right = right;
}
boolean isLeaf() {
return left == null;
}
@Override
public int compareTo(Node o) {
return Integer.compare(freq, o.freq);
}
}
static Node tree(Map<String, Integer> freq) {
if (freq.isEmpty()) {
throw new IllegalArgumentException("need at least one symbol");
}
PriorityQueue<Node> pq = new PriorityQueue<>();
for (var e : freq.entrySet()) {
pq.offer(new Node(e.getKey(), e.getValue(), null, null));
}
while (pq.size() > 1) {
Node a = pq.poll();
Node b = pq.poll();
pq.offer(new Node(null, a.freq + b.freq, a, b));
}
return pq.poll();
}Assign codes with a depth-first walk. Empty prefix on a leaf is the one-symbol alphabet.
static Map<String, String> codes(Node root) {
Map<String, String> out = new HashMap<>();
assign(root, "", out);
return out;
}
static void assign(Node n, String prefix, Map<String, String> out) {
if (n.isLeaf()) {
out.put(n.sym, prefix.isEmpty() ? "0" : prefix);
return;
}
assign(n.left, prefix + "0", out);
assign(n.right, prefix + "1", out);
}Encode the window by lookup. Decode by walking the tree one bit at a time until a leaf, emit, repeat. String-concatenated "0"/"1" is the lab. Production bit-packing is BitSet or a byte[] cursor — not a different algorithm.
Note: poll() on an empty heap is null. The empty-map throw keeps size() > 1 honest. Do not sort the node list on every merge.
Complexity
Let n be distinct symbols (alphabet), m the stream length. The heap is size n, not m.
| What | Cost | Why |
|---|---|---|
| Build tree | O(n log n) | n − 1 merges; each poll/offer is O(log n) |
| Assign codes | O(n) | One visit per tree node |
| Encode stream | O(m) after the table | Lookup per symbol (plus writing the bits) |
| Extra space | O(n) | Forest / tree and the code map |
| Naive rival | O(n!) tables | Enumerating prefix-free assignments |
The thirty-line window is m. Quoting O(n log n) for “compress the log” while n = 5 hides the linear scan that built the counts. Count is O(m); the interesting bill is the alphabet heap.
One min-heap, n − 1 parents, no JDK Huffman type. Re-sorting the forest after every merge is the wrong default once n is more than a handful.
When not to use Huffman
Skip this tree when the job is not “static prefix-free code from a known frequency table.”
- You needed gzip / zip / DEFLATE. Repeated phrases and a sliding window are LZ77. Huffman may run after that. It does not replace it.
- Frequencies are unknown or drift. This sketch is two-pass. A live stream that must encode before the table exists wants adaptive methods or a fixed agreed code. Do not pretend one snapshot Huffman table is a protocol.
- The alphabet is flat. Equal frequencies make Huffman lengths nearly uniform. Fixed-width is simpler and matches. Huffman still works; it is not earning its keep.
- You needed fractional bits. Huffman emits whole bits per symbol. Arithmetic or ANS coding is the next entropy family, not a flag on this heap.
- The wire format demands canonical codes. JPEG and DEFLATE specify how lengths become bit strings. Build lengths here; pack as the spec says. Do not invent labels and call it interoperable.
- You wanted secrecy. A public frequency table and a public tree are not encryption.
Prefix-free on independent symbols — that is the job. Knapsack, coin change, LCS, edit distance, and backtracking are other Wave 6 procedures. Interval scheduling is the next greedy, not a Huffman variant. Do not open those labs here.
Cheat sheet
Job: prefix-free code from a known frequency table
Procedure: min-heap of leaves; merge two lightest until one root
Codes: walk left=0 / right=1; one-symbol alphabet → "0"
Cost: minimize Σ freq(s) · |code(s)| (average length)
Greedy: two rarest as deepest siblings; then recurse on the parent
Time/space: O(n log n) / O(n) for alphabet n; encode stream O(m)
JDK: PriorityQueue; no Huffman class
Not this: gzip, zip, DEFLATE, LZ77, adaptive Huffman, arithmetic codingDo:
- Count first. Heap the alphabet. Merge lightest pair until one tree.
- Keep the code prefix-free by construction — the tree is the proof.
- Handle empty (throw) and singleton (
"0") at the method boundary. - Use
PriorityQueue; do not re-sort after every parent.
Don’t:
- Assign overlapping prefixes (
0and00) and hope a delimiter appears. - Call this gzip, zip, or DEFLATE. The sliding window is a different compressor.
- Quote
O(n log n)as the cost of encodingmsymbols without the count pass. - Re-lecture sift-up. Point at the heap and
PriorityQueueposts.
Wrap-up
Huffman replaces equal-width bits with a tree grown from frequencies: poll two lightest, parent them, repeat. The codes are the root-to-leaf paths. Prefix-free is free if you only emit at leaves. Greedy is optimal for that average length on a known independent-symbol table. It is not a general compressor, not a zip file, and not LZ77. Build the table, heap the symbols, walk the bits.
The layout was already a frequency map. The procedure is this heap. When the job is a sliding window of duplicates, that is LZ77 and DEFLATE. When the next greedy throws ranges away instead of merging weights, that is interval scheduling.