Тонкая куча

Тонкая куча — это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и фиббоначиева куча, но имеющая большую практическую ценность из-за меньших констант.

Тонкие кучи, как и многие другие кучеобразные структуры, аналогичны биномиальным кучам.

Тонкое дерево

Определение:

Тонкое дерево (thin tree) [math]T_k[/math] ранга [math]k[/math] — это дерево, которое может быть получено из биномиального дерева [math]B_k[/math] удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына.

Заметим, что у листьев детей нет, а если у корня [math]B_k[/math] удалить самого левого сына, то [math]B_k[/math] превратится в [math]B_{k-1}[/math]. Ранг тонкого дерева равен количеству детей корня.

Для любого узла [math]x[/math] в дереве [math]T_k[/math] обозначим: [math]Degree(x)[/math] — количество детей узла [math]x[/math]; [math]Rank(x)[/math] — ранг соответствующего узла в биномиальном дереве [math]B_k[/math].

Свойства тонкого дерева

Утверждение:

Для любого узла [math]x[/math] либо [math]Degree(x)=Rank(x)[/math], в этом случае говорим, что узел [math]x[/math] не помечен (полный); либо [math]Degree(x)=Rank(x)-1[/math], в этом случае говорим, что узел [math]x[/math] помечен (неполный).

Утверждение:

Корень не помечен (полный).

Утверждение:

Для любого узла [math]x[/math] ранги его детей от самого правого к самому левому равны соответственно [math]0,1,2,...,Degree(x)-1[/math].

Утверждение:

Узел [math]x[/math] помечен тогда и только тогда, если его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1 и он не имеет детей.

Тонкая куча

Определение:

Тонкий лес (thin forest) — это набор тонких деревьев, ранги которых не обязательно попарно различны.

Утверждение:

Для любого натурального числа [math]n[/math] существует тонкий лес, который содержит ровно [math]n[/math] элементов и состоит из тонких деревьев попарно различных рангов.

[math]\triangleright[/math]

Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо.

[math]\triangleleft[/math]

Определение:

Тонкая куча (thin heap) — это кучеобразно нагруженный тонкий лес.

Пусть [math]D(n)[/math] — максимально возможный ранг узла в тонкой куче, содержащей [math]n[/math] элементов.

Теорема (О максимальном ранге узла):

В тонкой куче из [math]n[/math] элементов [math]D(n) \leqslant \log_{\Phi} n[/math], где [math]\Phi=\frac{1+\sqrt{5}}{2}[/math] — золотое сечение.

Доказательство:

[math]\triangleright[/math]

Сначала покажем, что узел ранга [math]k[/math] в тонком дереве имеет не менее [math]F_k \geqslant \Phi^{k-1}[/math] потомков, включая самого себя, где [math]F_k[/math] — [math]k[/math]-е число Фибоначчи, определяемое соотношениями [math]F_0=1[/math], [math]F_1=1[/math], [math]F_k=F_{k-2}+F_{k-1}[/math] для [math]k \geqslant 2[/math]. Действительно, пусть [math]T_k[/math] — минимально возможное число узлов, включая самого себя, в тонком дереве ранга [math]k[/math]. По свойствам [math]1[/math] и [math]3[/math] тонкого дерева получаем следующие соотношения: [math]T_0=1,T_1=1,T_k \geqslant 1+\sum_{i=0}^{k-2}T_i[/math] для [math]k \geqslant 2[/math] Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что [math]T_k \geqslant F_k[/math] для любых [math]k[/math]. Неравенство [math]F_k \geqslant \Phi^{k-1}[/math] хорошо известно. Теперь убедимся в том, что максимально возможный ранг [math]D(n)[/math] тонкого дерева в тонкой куче, содержащей [math]n[/math] элементов, не превосходит числа [math]\log_{\Phi}(n)+1[/math]. Действительно, выберем в тонкой куче дерево максимального ранга. Пусть [math]n^*[/math] — количество вершин в этом дереве, тогда [math]n \geqslant n^* \geqslant \Phi^{D(n)-1}[/math]. Отсюда следует, что [math]D(n)\leqslant\log_{\Phi}(n)+1[/math].

[math]\triangleleft[/math]

Представление тонкой кучи

Поскольку при работе с тонкой кучей ссылка на родителя требуется только у самого левого ее ребенка, можно хранить ее вместо ссылки на левого сына этой вершины.

Таким образом, для эффективной работы тонкой кучи необходимы следующие поля узла:

• [math]key[/math] — ключ (вес) элемента;
• [math]child[/math] — указатель на самого левого ребенка узла;
• [math]right[/math] — указатель на правого брата узла, либо на следующий корень, если текущий узел корень;
• [math]left[/math] — указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это первый корень списка;
• [math]rank[/math] — ранг узла (количество дочерних узлов данного узла).

Отдельно должен храниться односвязный список корней, корень с минимальным ключом должне быть первым в этом списке.

Для ускорения проверки на тонкость (thinness) можно отдельно хранить помеченность вершины.

Также в вершине можно хранить любую дополнительную информацию.

Операции над тонкой кучей

Рассмотрим операции, которые можно производить с тонкой кучей. Время работы указано в таблице:

[math]makeHeap[/math]	[math]O(1)[/math]
[math]insert[/math]	[math]O(1)[/math]
[math]getMin[/math]	[math]O(1)[/math]
[math]meld[/math]	[math]O(1)[/math]
[math]extractMin[/math]	[math]O(\log(n))[/math]
[math]decreaseKey[/math]	[math]O(1)[/math]
[math]delete[/math]	[math]O(\log(n))[/math]

Многие операции над тонкой кучей выполняются так же, как и над фиббоначиевой.

makeHeap

Возвращаем новый пустой корневой список. Время [math]O(1)[/math].

insert

Создаем новое тонкое дерево из единственного узла с ключом [math]x[/math], добавляем в корневой список на первое место, если ключ минимален, иначе на второе. Время [math]O(1)[/math].

getMin

Обращаемся к первому корневому узлу списка. Время [math]O(1)[/math].

meld

Сливаем корневые списки, ставя первым тот список, где ключ первого корня минимален. Время [math]O(1)[/math].

extractMin

Удаляем корень с минимальным ключом из корневого списка, затем для всех его тонких детей уменьшаем ранг и делаем их нормальными, после чего сливаем детей с корневым списком и объединяем, пока возможно, тонкие деревья одного ранга. Время [math]O(\log(n))[/math].

decreaseKey

Время [math]O(1)[/math].

delete

Сначала выполняем [math]decreaseKey[/math] этого элемента до [math]-\infty[/math], затем выполняем [math]extractMin[/math]. Время [math]O(\log(n))[/math].

Источники

• Тонкие кучи — INTUIT.ru
• Haim Kaplan, Robert E. Tarjan Thin Heaps, Thick Heaps ACM Transactions on Algorithms - TALG , vol. 4, no. 1, pp. 1-14, 2008