Классическим способом ускорения алгоритма Хаффмана является слияние с виртуальным списком.
А именно, заводятся два списка — исходный и очередь.
В начала алгоритма исходный список сортируется по возрастанию частот, очередь пуста.
В процессе работы поддерживается следующий инвариант — элемент с минимальной частотой лежит либо в начале очереди, либо в начале исходного списка.
Шаг алгоритма следующий: извлекаются два минимальных элемента (оба из исходного списка, оба из очереди лили один из исходного, а второй из очереди) и «склеиваются», результат помещается в конец очереди.
Когда в обоих списках остался последний элемент — требуемое дерево построено.
