Huffman coding

Huffman coding is a greedy algorithm that repeatedly merges the two lowest-frequency nodes, so the first structural decision is how to maintain that ordering efficiently. A naïve approach sorts after every merge and costs O(n² log n); a min-heap keeps the minimum at the root and restores the heap property in O(log n) per operation, giving O(n log n) total. Before coding the tree, implement a generic MinHeap<T> parameterised on a comparator — this forces you to separate the priority policy from the node type and makes the heap reusable for any future greedy algorithm. Count symbol frequencies from a plain string by iterating once (O(n)); initialise one heap node per distinct symbol; verify the heap correctly returns the node with the lowest frequency on each extraction. Think about tie-breaking now: if two nodes have identical frequencies the extraction order determines the tree shape and, thus, the code strings. Pick a stable, deterministic rule — for example, prefer the node with the lexicographically smaller symbol, or prefer leaf over internal node — and document it, because the round-trip test will depend on it.

With the min-heap ready, implement the classic Huffman construction: extract the two nodes with the lowest frequencies, create an internal node whose frequency is their sum, push that internal node back into the heap, and repeat until one node remains — that is the root. The algorithm is purely greedy and provably optimal by an exchange argument: if any other tree were better, you could swap its two deepest-sibling leaves with the two lowest-frequency symbols and reduce the expected code length, contradicting the assumption. The edge case that most implementations miss is the single-distinct-symbol alphabet (e.g. 'aaaa'): the loop never fires because only one node ever existed, so the root is a leaf, and you must assign it an explicit code (conventionally '0') so encoding and decoding still work. Another subtle point: your internal nodes do not carry a symbol — only leaves do. Make this a strict type invariant now, because the decode traversal relies on it.

Turn the tree into a code table by DFS: go left → append '0', go right → append '1', emit (symbol, accumulated-bits) at each leaf. The resulting codes are prefix-free by construction — no code is a prefix of another because codes only live at leaves, and any prefix of a leaf-path is an internal node. Prove this to yourself: if code A were a prefix of code B, you could follow A in the tree and reach a leaf, but then B's remaining bits would have to descend from a leaf, which has no children — contradiction. Write a property test that exhaustively checks all pairs in your code table: for every (a, b) pair where a ≠ b, assert that neither a.startsWith(b) nor b.startsWith(a). This is the most important correctness invariant in the whole project. Also verify that shorter codes go to higher-frequency symbols: Huffman's optimality guarantee states the code-length assignment is monotonically non-increasing with frequency, so if freq(x) > freq(y) then len(code(x)) ≤ len(code(y)). This is a second property test, and it catches tree-construction bugs that a round-trip alone would miss.

Encoding is the straightforward half: look up each symbol in the code table, concatenate the bit strings, and return the result. The interesting questions are about what happens when you integrate this into a real compressor. First, the bit string you produce here is conceptual — each character is a '0' or '1', not a packed bit — which means your output is 8× larger than the raw bytes before you pack it. For this project a string-of-characters representation is fine because it lets you focus on the algorithm, but document the gap: a production encoder would pack bits into bytes, manage the final partial byte with a pad bit count, and prepend the code table (or a canonical form of it) as a header so the decoder can reconstruct without out-of-band knowledge. Second, your encode function takes a pre-built code table, not the original tree — this is intentional, because decoding needs the tree (to follow branches) while encoding only needs the leaf-label-to-bits map. Keep the two interfaces separate. Third, measure compression: count the total bit length of the encoded output and compare it with a fixed-width baseline of ceil(log2(alphabet_size)) bits per symbol. For any input with a skewed frequency distribution, Huffman's output must be strictly shorter — if it is not, your tree is wrong.

Decoding is the inverse: start at the root, read one bit, descend left on '0' or right on '1', and emit the leaf's symbol whenever you reach a leaf, then reset back to the root. This traversal is O(output_length × average_code_length) and does not require a hash lookup, which is why the tree is the right data structure for decoding even though the map is right for encoding. The correctness of decoding is guaranteed by the prefix-free property: because no code is a prefix of another, the first leaf you hit is always unambiguously the intended symbol. If your prefix-free test from the previous milestone passes, decode is trivially correct given a correct implementation of the traversal. The interesting failure mode is the single-distinct-symbol case again: the root is a leaf with no children, so the 'descend on bit' loop never fires — you must special-case it to emit the symbol for every bit in the input. Write a round-trip property: for any string s built from a known alphabet, decode(encode(s, codes), tree) === s. This is your integration test, and it subsumes unit tests on both encode and decode individually.

Now that encode/decode works, reason about what 'optimal' actually means and how to make the code table transmissible without the tree. Huffman's algorithm minimises the expected code length E[L] = Σ freq(x) × len(code(x)), which equals the weighted path length from root to all leaves. The exchange argument proves this: in an optimal tree the two lowest-frequency symbols must be siblings at the deepest level — if they were not, you could swap them with the actual deepest siblings and reduce E[L], contradicting optimality. Entropy H(X) = -Σ p(x) × log₂(p(x)) is the lower bound: no uniquely decodable code can achieve expected length below H(X) bits per symbol. Compute both E[L] and H(X) for 'abracadabra' and compare — Huffman comes within a few percent. Next, canonical Huffman codes: reassign codes so that (a) codes of the same length are contiguous and (b) within a length group symbols are sorted alphabetically, and the codes themselves are assigned as consecutive integers in binary. The canonical form encodes the same lengths as the original tree but with shorter codes on average for transmission — you only need to send the symbol→length mapping (not the tree), and any decoder can reconstruct the canonical codes from that. Implement codes_canonical(tree) returning the canonical bit strings.