Deterministic binary Huffman coding

Input: A finite full-support source $(m,p)$ as in Finite discrete sources and product blocks, with the symbols ordered $1,\dots ,m$.

Output: A binary prefix code $C_H$ on these symbols.

If $m=1$, return the one-bit codeword $C_H(1)=0$.

If $m\ge 2$, make one active leaf for each source symbol $i$, with weight $p_i$ and serial number $i$. Repeatedly do the following while more than one node is active:

1. Order active nodes lexicographically by (weight, serial number), using the ordinary order on real weights and then integer serials.
2. Remove the first two nodes. Make a new parent whose left child is the first removed node and whose right child is the second, whose weight is their sum, and whose serial is the next unused integer.
3. Insert this parent among the active nodes.

When one root remains, label every left edge $0$ and every right edge $1$. The codeword for symbol $i$ is the edge-label sequence on the path from the root to its original leaf. The order by serial number fixes all ties and fixes the bit orientation. The same merge rule applies to any finite active list of positive weights carrying distinct serial numbers; the source input initializes the serials as $1,\dots ,m$, and each new parent receives a fresh serial.

For each $m\ge 2$, the algorithm executes exactly $m-1$ merges because each merge decreases the number of active nodes by one. The returned tree is finite. The next theorem proves the code is prefix-free and optimal; no complexity bound is asserted.