73
правки
Изменения
м
→Обоснование алгоритма Ху-Таккера
Вершину <tex>t</tex> назовем горой между двумя впадинами.
Из [[#lemma3|леммы 3]] следует, что можно образовать две отдельных очереди — одну для каждой впадины. Из-за горы узлы вершины из разных впадин не совместимы между собой. Когда наименьшие новые вершины(полученные в результате слияния) во впадинах станут достаточно большими, гора будет наконец скомбинирована. С этого момента все новые вершины станут совместимыми. Получается слияние двух очередей. По существу, фаза 1 в алгоритме Ху-Таккера подобна слиянию нескольких очередей, а произвольную последовательность весов можно рассматривать как соединение нескольких впадин.
Чтобы понять, почему последовательность уровней может быть соединена в алфавитное дерево, достаточно рассмотреть два случая:
*Комбинируются две вершины <tex>a</tex> и <tex>e</tex> из разных впадин. Пусть при этом между <tex>a</tex> и <tex>e</tex> расположены новые вершины <tex>b,c,d</tex> {{---}} каждая из них имеет двух сыновей, скажем, <tex>b1</tex> и <tex>b2</tex>, <tex>c1</tex> и <tex>c2</tex>, <tex>d1</tex> и <tex>d2</tex> {{---}} когда комбинируются <tex>a</tex> и <tex>e</tex>, мы в действительности создаем общего отца для <tex>a</tex> и <tex>b1</tex>. После этого общего отца получают <tex>b2</tex> и <tex>c1</tex>, затем <tex>c2</tex> и <tex>d1</tex>. Наконец, общего отца получают <tex>d2</tex> и <tex>e</tex>.
Заметим, что это лишь обоснование, а не строгое доказательство, его задача дать понимания понимание правдивости алгоритма.
== Корректность алгоритма Ху-Таккера ==
