Строим дерево от листьев к корню, беря в первую очередь вершины с минимальной частотой и добавляя новые по мере их образования. Как образуем: берём 2 штуки с мин частотой, сливаем в одно (суммируем) и добавляем новый символ в priority queue со всеми частотами. И так далее.
Нужны фиктивные буквы с нулевыми вероятностями. Их количество s вычиялется так:
минимальное $s = m*(|B|-1)-|P|-1)\text{; } s,m \in ℕ \text{, } s \ge 0$
или, что эквивалентно:
$s = min_{m \in ℕ} \{m*(|B|-1)-|P|-1\}, s \ge 0$
Где B = k, P - набор вероятностей (частот)
Штук уже берём k на каждом шаге