Pseudocode
Huffman’s algorithm builds a Huffman tree bottom-up, and in every iteration it merges the two trees that have the smallest sums of corresponding symbol frequencies.
Pseudocode
- Input: a nonnegative frequency $p_a$ for each symbol $a$ of an alphabet $\Sigma$.
- Output: the Huffman tree with minimum average leaf depth, representing the prefix-free binary code with minimum average encoding length.
// Initialization
for each $a \in \Sigma$ do:
$T_a :=$ tree containing one node, labeled $a$
$\mathcal{F} := \lbrace T_a \rbrace_{a \in \Sigma}$ // invariant: $\forall T \in \mathcal{F}, P(T) = \sum_{a \in T} p_a$
// Main loop
while $\mathcal{F}$ contains at least two trees do:
$T_1 := \argmin_{T \in \mathcal{F}} P(T)$ // min frequency sum
$T_2 := \argmin_{T \in \mathcal{F}, T \ne T_1} P(T)$ // second-smallest
remove $T_1$ and $T_2$ from $\mathcal{F}$
// roots of $T_1$, $T_2$ become left, right
// children of a new internal node
$T_3 :=$ merger of $T_1$ and $T_2$
$P(T_3) := P(T_1) + P(T_2)$ // maintains invariant
add $T_3$ to $\mathcal{F}$
return the unique tree in $\mathcal{F}$
Last updated 09 May 2025, 23:43 +0500 .