Основные определения
Рассматриваемые здесь тонкие и, в следующей лекции, толстые кучи предложены М.Фредманом и Х.Капланом как альтернатива фибоначчиевым кучам. Долгое время фибоначчиевы кучи считались рекордными по производительности. Оценки операций над фибоначчиевыми кучами имеют амортизационный характер, а скрытые в них константы велики настолько, что реальный выигрыш во времени работы с ними достигался только на данных "астрономических" размеров. Рассматриваемые здесь тонкие кучи имеют те же асимптотические оценки, что и фибоначчиевы, но гораздо практичнее их. Оценки для толстых куч "хуже" по операции слияния, выполняемой за O(\log n) времени. Достоинством этой структуры является то, что ее оценки рассчитаны на худший случай. Заметим, что на данный момент ни фибоначчиевы, ни толстые, ни тонкие кучи не являются рекордными, так как Г.Бродал предложил новую структуру, которую мы будем называть кучей Бродала. Кучи Бродала характеризуется такими же, как и фибоначчиевы кучи, оценками операций, но все оценки справедливы для худшего случая. К сожалению, структура, предложенная Г.Бродалом, сложна для реализации. Рассмотрим реализацию приоритетной очереди с помощью тонкой кучи.
Тонкие кучи, как и многие другие кучеобразные структуры, аналогичны биномиальным кучам.
Тонкое дерево
ранга — это дерево, которое может быть получено из биномиального дерева
удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына. Заметим, что у листьев детей нет, а если у корня удалить самого левого сына, то
превратится в . Ранг тонкого дерева равен количеству детей корня.
Для любого узла в дереве обозначим: — количество детей узла ; — ранг соответствующего узла в биномиальном дереве .
Тонкое дерево удовлетворяет следующим условиям:
- Для любого узла либо , в этом случае говорим, что узел не помечен (полный); либо , в этом случае говорим, что узел помечен (неполный).
- Корень не помечен (полный).
- Для любого узла ранги его детей от самого правого к самому левому равны соответственно .
- Узел помечен тогда и только тогда, если его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1 и он не имеет детей.
На рис. 8. 1 приведены примеры тонких деревьев; числа рядом с узлами обозначают их ранги. Вверху изображено биномиальное дерево , внизу — два полученных из тонких дерева ранга три. Стрелки указывают на помеченные узлы. Заметим, что биномиальное дерево является тонким деревом, у которого все узлы не помечены.
Тонкий лес — это набор тонких деревьев, ранги которых не обязательно попарно различны.
Рис. 8.1.
Тонкая куча — это кучеобразно нагруженный тонкий лес.
Заметим, что в тонкой куче могут встречаться тонкие деревья одинакового ранга, в то время как в биномиальной куче все деревья должны иметь попарно различные ранги.
Утверждение. Для любого натурального числа существует тонкий лес, который содержит ровно элементов и состоит из тонких деревьев попарно различных рангов.
Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо.
Пусть — максимально возможный ранг узла в тонкой куче, содержащей элементов.
Теорема [22]
В тонкой куче из элементов , где — золотое сечение.
Доказательство. Сначала покажем, что узел ранга
в тонком дереве имеет не менее потомков, включая самого себя, где — -е число Фибоначчи, определяемое соотношениями , , для .
Действительно, пусть — минимально возможное число узлов, включая самого себя, в тонком дереве ранга . По свойствам и
тонкого дерева получаем следующие соотношения:
Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что для любых . Неравенство
хорошо известно.
Теперь убедимся в том, что максимально возможный ранг
тонкого дерева в тонкой куче, содержащей элементов, не превосходит числа . Действительно, выберем в тонкой куче дерево максимального ранга. Пусть — количество вершин в этом дереве, тогда .
Отсюда следует, что .
