63
правки
Изменения
Нет описания правки
|definition =
Пусть у нас есть отсортированный по возрастанию алфавит <tex>\Sigma = \{a_1, a_2, \cdots, a_n\}</tex>, <tex>|\Sigma| = n</tex>. Где <tex>a_i</tex> {{---}} число вхождений символа в строку.
Требуется построить [[Алгоритм_Хаффмана | код Хаффмана ]] за <tex>O(n)</tex>.
}}
Eсли массив не отсортирован, то это можно сделать, например,[[Цифровая_сортировка | цифровой сортировкой]] за <tex> O(n) </tex>, что не ухудшит асимптотику.
Идея алгоритма заключается в том, чтобы создать такую [[Дискретная_математика,_алгоритмы_и_структуры_данных#.D0.9F.D1.80.D0.B8.D0.BE.D1.80.D0.B8.D1.82.D0.B5.D1.82.D0.BD.D1.8B.D0.B5_.D0.BE.D1.87.D0.B5.D1.80.D0.B5.D0.B4.D0.B8 | очередь с приоритетами]], из которой можно было бы доставать два минимума за <tex> O(1) </tex>, после чего в эту же очередь с приоритетами положить их сумму за <tex> O(1) </tex>. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных. На каждой итерации мы будет будем выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.
У нас есть три варианта возможных пар минимумов :
Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы.
Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных.
На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно <tex>n</tex> итераций.
'''int''' HuffmanCoding(a: '''int[0..n]'''):
b: '''int[0..n]'''
i, j, inf, ans: '''int''' ''<font color=green>// i, j {{---}} указатели в массивах, inf {{---}} большое число</font>''
'''for''' k = 0 '''to''' n
b[k] = inf<tex>\infty</tex>
'''for''' k = 0 '''to''' n - 1
'''if''' a[i] + a[i + 1] <= a[i] + b[j] && a[i] + a[i + 1] <= b[j] + b[j + 1]
