40
правок
Изменения
→Алгоритм Хаффмана за O(n) .
В алгоритме <tex> n </tex> итерации, так как на каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время.
==Реализация==
Поскольку мы не ограничены по памяти, очень удобно использовать вместо двух одномерных массивов один двумерный. Это избавит код от громоздких "if".
sum = int[logMAXN][MAXN+1] // массив, в котором считаем суммы, сначала заполнен "бесконечностями"
s1, s2 // указатели на строки, которые выполняют функции первого и второго массивов в описании алгоритма
h1, h2 // указатели на первый элемент первой строки и второй строки соответственно
t1, t2 // указатели на ячейки массивов сразу после последнего элемента в этих массивах
'''while''' chek < n
'''while''' h1 < t1 // проходим по массиву, выполняющему роль первого; внутри этого цикла мы ищем минимумы и записываем суммы
'''if''' h2 == t2
sum[s2][t2] = sum[s1][h1] + sum[s1][h1+1]
'''if''' t1 - h1 == 1
sum[s2][t2] = sum[s2][t2] - sum[s1][h1+1]
h1 = h1 + 2
t2++
'''else'''
'''if''' sum[s1][h1] < sum[s2][h2]
'''if''' sum[s1][h1+1] < sum[s2][h2]
sum[s2][t2] = sum[s1][h1] + sum[s1][h1+1]
h1 += 2
'''else'''
sum[s2][t2] = sum[s1][h1] + sum[s2][h2]
h1++
h2++
t2++
'''else'''
'''if''' sum[s1][h1] < sum[s2][h2+1]
sum[s2][t2] = sum[s2][h2] + sum[s1][h1]
h1++
h2++
'''else'''
sum[s2][t2] = sum[s2][h2] + sum[s2][h2+1]
h2+=2
t2++
chek++ // учитываем то, что элементов стало на 1 меньше
s1 = s2 // строки меняются ролями, соответственно все их параметры тоже
h1 = h2
t1 = t2
s2++
h2 = t2 = 0
