40
правок
Изменения
м
sum = int[logMAXN][MAXN+1] // массив, в котором считаем суммы, сначала заполнен "бесконечностями"
temp // переменная, на которую ссылаются самые нижние листья дерева
→Пример
На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно <tex>n</tex> итераций.
==Пример==
Для примера возьмем строку "абракадабра".
{| class="wikitable"
! Буква || д || к || б || р || а
|-
| Массив 1 || 1 || 1 || 2 || 2 || 5
|-
| Массив 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
|}
На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив.
{| class="wikitable"
| Массив 1 || used || used || 2 || 2 || 5
|-
| Массив 2 || 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
|}
На втором шаге снова суммируются первые две ячейки первого массива(нам все равно что взять, первый элемент второго массива или второй элемент первого).
{| class="wikitable"
| Массив 1 || used || used || used || used || 5
|-
| Массив 2 || 2 || 4 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
|}
На третьем шаге два минимальных элемента - это первые две ячейки второго массива.
{| class="wikitable"
| Массив 1 || used || used || used || used || 5
|-
| Массив 2 || deleted || deleted || 6 || <tex>\infty</tex> || <tex>\infty</tex>
|}
На четвертом шаге складываются две оставшиеся ячейки.
{| class="wikitable"
| Массив 1 || used || used || used || used || used
|-
| Массив 2 || deleted || deleted || deleted || 11 || <tex>\infty</tex>
|}
==Реализация==
Поскольку мы не ограничены по памяти, очень удобно использовать вместо двух одномерных массивов один двумерный. Это избавит код от громоздких "if".
n // количество элементов
s1 = 0, s2 = 1 // указатели на строки, которые выполняют функции первого и второго массивов в описании алгоритма
h1 = 0, h2 = 0 // указатели на первый элемент первой строки и второй строки соответственно
t1 = n, t2 = 0 // указатели на ячейки массивов сразу после последнего элемента в этих массивах
check = 0 // считает на сколько стало меньше элементов
class vert{ // класс - лист дерева, которое, по сути, строится в коде хаффмана
public:
};
sum = vert[logMAXN][MAXN+1] // элементы w каждой ячейки равны "бесконечности"
temp = vert // переменная, на которую ссылаются самые нижние листья дерева
temp.check = -1
make(int str1, int str2, int pos1, int pos2)// функция, которая суммирует, задает указатели и значения переменных val и left
sum[s2][t2].w = sum[str1][pos1].w + sum[str2][pos2].w
