Frequencies guide code lengths
Fixed-width coding gives every symbol the same bit allowance despite unequal frequencies. Huffman permits different lengths and minimizes the sum of each frequency multiplied by its codeword length.
Concatenated codewords must remain decodable. Placing symbols at binary-tree leaves makes root-to-leaf bit paths prefix-free. Shortening frequent symbols must therefore respect the structure of the complete tree.
Repeatedly merging the two lightest trees
Construction starts with one frequency-weighted leaf per occurring symbol. Repeatedly remove the two lightest trees, join them under a parent of their combined weight, and return that parent to the candidates. A priority queue supports these selections.
Tied weights can produce different equally optimal codebooks, and swapping left and right branches changes bit strings without changing lengths. Encoder and decoder must share the actual tree rather than merely agree that both use Huffman.
References: [1]
The scope of optimality and overhead
For given weights, the optimum concerns symbol-by-symbol binary prefix-code length. Context or repeated phrases can still be exploited by other models, so it is not a universal best-compression theorem.
Files also need tree and termination information. Princeton writes the tree and original byte count before encoded payload and uses them to decode. On short messages this metadata can exceed payload savings, so complete representation size matters.