Псевдокод
Алгоритм Хаффмана строит дерево Хаффмана «снизу вверх» и на каждой итерации объединяет два дерева с наименьшими суммами частот соответствующих символов.
Псевдокод
- Вход: неотрицательная частота $p_a$ для каждого символа $a$ из алфавита $\Sigma$.
- Выход: дерево Хаффмана с минимальной средней глубиной листьев, задающее беспрефиксный двоичный код с минимальной средней длиной.
// Инициализация
for each $a \in \Sigma$ do:
$T_a :=$ tree containing one node, labeled $a$
$\mathcal{F} := \lbrace T_a \rbrace_{a \in \Sigma}$ // инвариант: $\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)$ // минимальная сумма частот
$T_2 := \argmin_{T \in \mathcal{F}, T \ne T_1} P(T)$ // второе по величине
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)$ // инвариант сохраняется
add $T_3$ to $\mathcal{F}$
return the unique tree in $\mathcal{F}$
Last updated 09 мая 2025, 23:43 +0500 .