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