Тонкая куча

Из биномиального дерева ранга 3 получены два тонких дерева. Числа обозначают ранг вершин, черные вершины являются помеченными (не имеют самого левого сына).

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

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

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

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

Тонкое дерево (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]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]

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

Для амортизационного анализа операций применим метод потенциалов.

Пусть функция потенциала определена как [math]\Phi = n + 2 \cdot m[/math] где [math]n[/math] — это количество тонких деревьев в куче, а [math]m[/math] — это количество помеченных вершин.

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

Определённый таким образом потенциал обладает свойствами: [math]\Phi \geqslant 0[/math]. Для пустой тонкой кучи [math]\Phi = 0[/math].

makeHeap

Для создания новой пустой тонкой кучи нужно вернуть ссылку на новый пустой корневой список, его потенциал [math]\Phi=0[/math].

Стоимость [math]O(1)[/math].

insert

Для вставки элемента в тонкую кучу нужно создать новое тонкое дерево из единственного узла с ключом [math]x[/math], добавить его в корневой список на первое место, если этот ключ минимален, иначе на второе. Потенциал [math]\Phi[/math] увеличивается на 1.

Стоимость [math]O(1)[/math].

getMin

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

Стоимость [math]O(1)[/math].

meld

Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал [math]\Phi[/math] не меняется.

Стоимость [math]O(1)[/math].

extractMin

Чтобы извлечь минимальный элемент из тонкой кучи нужно:

1. Удалить корень с минимальным ключом из корневого списка.
2. Уменьшить ранг для всех его помеченных детей.
3. Cлить детей с корневым списком.
4. Объединять, пока возможно, тонкие деревья одного ранга.

Это можно сделать, например, с помощью вспомогательного массива размером [math]O(D(n))[/math], в [math]i[/math]-ой ячейке которого хранится корень тонкого дерева [math]T_i[/math] ранга [math]i[/math].

Изначально массив пуст, а мы добавляем в него все деревья нашего корневого списка.

При добавлении нового дерева мы, если дерево такого ранга уже есть в массиве, связываем его с существующим и пытаемся добавить новое дерево с рангом на [math]1[/math] больше.

Пусть мы сделали [math]ls[/math] связывающих шагов (linking steps) во время добавления в массив.

Мы удалили корень из списка за [math]O(1)[/math], затем за [math]O(D(n))[/math] нормализовали детей корня и добавили в корневой список, далее за [math]O(D(n))+ls[/math] получили новый корневой список, в котором за [math]O(D(n))[/math] нашли минимальный корень и подвесили список за него.

Получили фактическую стоимость [math]O(D(n))+ls[/math]. С другой стороны, при добавлении детей в список мы увеличили потенциал [math]\Phi[/math] не более чем на [math]O(D(n))[/math], а каждый связывающий шаг уменьшает наш потенциал [math]\Phi[/math] на [math]1[/math].

Cтоимость [math]O(D(n))=O(\log(n))[/math].

decreaseKey

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

Теперь могут быть нарушены свойства тонкого дерева, будем различать два вида нарушений:

• Братские нарушения — это нарушения третьего свойства тонкого дерева.
• Родительские нарушения — это нарушения первого или второго свойства тонкого дерева.

Назовем узел [math]y[/math] узлом локализации братского нарушения среди детей узла [math]z[/math], если ранг узла [math]y[/math] отличается от ранга его ближайшего правого брата на 2, либо он не имеет правого брата и его ранг равен 1.

Назовем узел [math]y[/math] узлом локализации родительского нарушения, если выполнено одно из трех условий:

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

Пусть узел [math]y[/math] — это узел локализации братского нарушения.

• Узел [math]y[/math] не помечен, тогда помещаем поддерево с корнем в самом левом сыне узла [math]y[/math] на место пропущенного в братском списке. Узел [math]y[/math] становится помеченным, дерево становится корректным, процедура исправления завершается.
• Узел [math]y[/math] помечен, тогда уменьшаем ранг узла [math]y[/math] на единицу. Теперь узлом локализации нарушения будет либо левый брат узла [math]y[/math], либо его родитель, тогда нарушение станет родительским.

С помощью этих действий мы избавились от братских нарушений, теперь разберем родительские.

Пусть узел [math]y[/math] — это узел локализации родительского нарушения, а узел [math]z[/math] — родитель узла [math]y[/math].

Переместим все поддерево с корнем в [math]y[/math] в корневой список и уменьшим ранг [math]y[/math].

• Узел [math]z[/math] не был помечен, пометим его, тогда дерево станет корректным.
• Узел [math]z[/math] был помечен, тогда [math]z[/math] — новый узел локализации родительского нарушения, переходим к нему.

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

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

Стоимость [math]O(1)[/math].

delete

Чтобы удалить элемент из тонкой кучи нужно сначала выполнить [math]decreaseKey[/math] этого элемента до [math]-\infty[/math], а затем выполнить [math]extractMin[/math].

Стоимость [math]O(\log(n))[/math].

Источники

• Тонкие кучи — INTUIT.ru
• Каплан Х., Тарьян А. Р.., Thin Heaps, Thick Heaps // ACM Transactions on Algorithms. — 2008. — Т.4. — №1. — C. 1—14. — ISSN: 1549-6325
• Станкевич А. С., Дополнительные главы алгоритмов, лекция 1 — Лекториум