Huffman Build

Build a Huffman code table from symbol frequencies.

Types

type Code struct {
    Bits uint32 // code bits stored in the low bits
    Len  uint8  // number of valid bits
}

func BuildHuffman(freqs []int) []Code

Behavior

• freqs[i] is the frequency of symbol i.
• Return a codes slice of the same length.
• For freqs[i] == 0, the code length must be 0.
• If exactly one symbol has non-zero frequency, assign it code length 1 with bits 0.

Tie-breaking (determinism)

When merging nodes with equal frequency, break ties by lower minimum symbol id in the subtree. For internal nodes, the minimum symbol id is the minimum of its children. The left child is the one that wins the tie-break.

Notes

• Use 0 for left edges and 1 for right edges.
• Bits stores the code in the lowest Len bits (MSB-first when writing).