Алгоритм Хаффмана за O(n)

Задача:

Пусть у нас есть отсортированный по возрастанию алфавит [math]\Sigma = \{a_1, a_2, \cdots, a_n\}[/math], [math]|\Sigma| = n[/math]. Где [math]a_i[/math] — число вхождений символа в строку. Требуется построить код Хаффмана за [math]O(n)[/math].

Описание алгоритма

Eсли массив не отсортирован, то это можно сделать, например, цифровой сортировкой за [math] O(n) [/math], что не ухудшит асимптотику.

Идея алгоритма заключается в том, чтобы создать такую очередь с приоритетами, из которой можно было бы доставать два минимума за [math] O(1) [/math], после чего в эту же очередь с приоритетами положить их сумму за [math] O(1) [/math]. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных. На каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.

У нас есть три варианта возможных пар минимумов :

1. Оба элемента из первого массива.
2. Первый элемент первого массива и первый элемент второго массива.
3. Два первых элемента второго массива.

Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы.

На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно [math]n[/math] итераций.

Пример

Для примера возьмем строку "абракадабра". [math]i, j[/math] — указатели на первые неиспользованные элементы в массиве 1 и 2, соответственно.

[math]i = 0, j = 0[/math]

Буква	д	к	б	р	а
Массив 1	1	1	2	2	5

Массив 2	[math]\infty[/math]	[math]\infty[/math]	[math]\infty[/math]	[math]\infty[/math]	[math]\infty[/math]

На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив.

[math]i = 2, j = 0[/math]

Буква	д	к	б	р	а
Массив 1	1	1	2	2	5

	дк
Массив 2	2	[math]\infty[/math]	[math]\infty[/math]	[math]\infty[/math]	[math]\infty[/math]

На втором шаге снова суммируются первые две ячейки первого массива(нам все равно что взять, первый элемент второго массива или второй элемент первого).

[math]i = 4, j = 0[/math]

Буква	д	к	б	р	а
Массив 1	1	1	2	2	5

	дк	бр
Массив 2	2	4	[math]\infty[/math]	[math]\infty[/math]	[math]\infty[/math]

На третьем шаге два минимальных элемента - это первые две ячейки второго массива.

[math]i = 4, j = 2[/math]

Буква	д	к	б	р	а
Массив 1	1	1	2	2	5

	дк	бр	дкбр
Массив 2	2	4	6	[math]\infty[/math]	[math]\infty[/math]

На четвертом шаге складываются две оставшиеся ячейки.

[math] i = 5, j = 3[/math]

Буква	д	к	б	р	а
Массив 1	1	1	2	2	5

	дк	бр	дкбр	адкбр
Массив 2	2	4	6	11	[math]\infty[/math]