Изменения

Перейти к: навигация, поиск
Построение кода Хаффмана
Алгоритм строит оптимальное дерево префиксных кодов. Для этого в цикле выполняется выборка из очереди двух вершин <math>\mathrm{x}</math> и <math>\mathrm{y}</math> с наменьшими частотами (<math>\mathrm{f[x]}</math> и <math>\mathrm{f[y]}</math> соответственно), которые заменяются на одну вершину <math>\mathrm{z}</math> с частотой <math>\mathrm{f[x]}</math> <math>\mathrm{+}</math> <math>\mathrm{f[y]}</math> и детьми <math>\mathrm{x}</math> и <math>\mathrm{y}</math>.
Алгоритм работает за <tex>{O(nlog(n)\log{n}})</tex> для алфавита из <math>\mathrm{n}</math> символов.
Анонимный участник

Навигация