63
правки
Изменения
Нет описания правки
| Массив 2 || 2 || 4 || 6 || 11 || <tex>\infty</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
'''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]
b[k] = a[i] + a[i + 1]
ans += b[k]
i += 2
'''continue'''
'''if''' a[i] + b[j] <= a[i] + a[i + 1] && a[i] + b[j] <= b[j] + b[j + 1]
b[k] = a[i] + b[j]
ans += b[k]
i++
j++
'''continue'''
'''if''' b[j] + b[j + 1] <= a[i] + a[i + 1] && b[j] + b[j + 1] <= a[i] + b[j]
b[k] = b[j] + b[j + 1]
ans += b[k]
j += 2
'''return''' ans
==См. также==
*[[Алгоритм Хаффмана]]
*[[Оптимальное хранение словаря в алгоритме Хаффмана]]