Тонкая куча
Тонкая куча — это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и фибоначчиева куча, но имеющая большую практическую ценность из-за меньших констант.
Тонкие кучи, как и многие другие кучеобразные структуры, аналогичны биномиальным кучам.
Содержание
Тонкое дерево
| Определение: |
| Тонкое дерево (thin tree) ранга — это дерево, которое может быть получено из биномиального дерева удалением самого левого сына у нескольких внутренних, то есть не являющихся корнем или листом, узлов. |
Ограничение на принадлежность внутренним узлам вызвано тем, что у листьев детей нет, а если у корня удалить самого левого сына, то превратится в .
| Утверждение: |
Ранг тонкого дерева равен количеству детей его корня. |
Для любого узла в дереве обозначим:
- — количество детей узла .
- — ранг соответствующего узла в биномиальном дереве .
Свойства тонкого дерева
| Утверждение: |
Тонкое дерево обладает следующими свойствами:
|
Тонкая куча
| Определение: |
| Тонкий лес (thin forest) — это набор тонких деревьев, ранги которых не обязательно попарно различны. |
| Утверждение: |
Для любого натурального числа существует тонкий лес, который содержит ровно элементов и состоит из тонких деревьев попарно различных рангов. |
| Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо. |
| Определение: |
| Тонкая куча (thin heap) — это кучеобразно нагруженный тонкий лес, то есть каждое тонкое дерево удовлетворяет условиям кучи. |
Пусть — максимально возможный ранг узла в тонкой куче, содержащей элементов.
| Теорема (О максимальном ранге узла): |
В тонкой куче из элементов , где — золотое сечение. |
| Доказательство: |
|
Сначала покажем, что узел ранга в тонком дереве имеет не менее потомков, включая самого себя, где — -е число Фибоначчи. Действительно, пусть — минимально возможное число узлов, включая самого себя, в тонком дереве ранга . По свойствам и тонкого дерева получаем следующие соотношения: для Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что для любых . Неравенство хорошо известно. Теперь убедимся в том, что максимально возможный ранг тонкого дерева в тонкой куче, содержащей элементов, не превосходит числа . Действительно, выберем в тонкой куче дерево максимального ранга. Пусть — количество вершин в этом дереве, тогда . Отсюда следует, что . |
Представление тонкой кучи
Тонкую кучу можно представить как односвязный список корней тонких деревьев, причем корень с минимальным ключом должен быть первым в списке.
Поскольку при работе с тонкой кучей ссылка на родителя требуется только у самого левого его ребенка, можно хранить ее вместо ссылки на левого брата этой вершины.
Таким образом, для эффективной работы тонкой кучи необходимы следующие поля узла:
- — ключ (вес) элемента;
- — указатель на самого левого ребенка узла;
- — указатель на правого брата узла, либо на следующий корень, если текущий узел корень;
- — указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это корень;
- — ранг узла.
Для ускорения проверки на тонкость (thinness) можно отдельно хранить тонкость вершины. Также в вершине можно хранить любую дополнительную информацию.
Для работы с тонкой кучей достаточно иметь односвязный список ее корней.
Операции над тонкой кучей
Рассмотрим операции, которые можно производить над тонкой кучей. Время работы указано в таблице:
Многие операции над тонкой кучей выполняются так же, как и над фиббоначиевой.
Для амортизационного анализа операций применим метод потенциалов.
Пусть функция потенциала определена как где — это количество тонких деревьев в куче, а — это количество тонких вершин.
| Утверждение: |
Определённый таким образом потенциал обладает свойствами:
|
Пусть — узел тонкого дерева, а — тонкая куча, причем содержит ссылки на первый и последний корень и соответственно.
Также введем вспомогательную функцию проверки узла на тонкость, для этого воспользуемся тем, что у левого сына узла ранг равен .
bool isThin(x)
if x.rank == 1
return x.child == null
else
return x.child.rank + 1 != x.rank
makeHeap
Для создания новой пустой тонкой кучи нужно вернуть ссылку на новый пустой корневой список, его потенциал .
ThinHeap makeHeap() H.first = null H.last = null return H;
Стоимость .
insert
Для вставки элемента в тонкую кучу нужно создать новое тонкое дерево из единственного узла с ключом , добавить его в корневой список на первое место, если этот ключ минимален, либо на последнее. Потенциал увеличивается на 1.
void insert(H, x)
if H.first == null
H.first = x
H.last = x
else
if x.key < H.first.key
x.right = H.first
H.first = x
else
H.last.right = x
H.last = x
Стоимость .
getMin
Для обращения к минимальному элементу в тонкой куче нужно обратиться к первому корневому узлу списка и вернуть его ключ, потенциал не меняется.
Node getMin(H) return H.first
Стоимость .
meld
Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал не меняется.
ThinHeap meld(H1, H2)
if H1.first == null
return H2
else
if H2.first == null
return H1
else
if H1.first.key < H2.first.key
H1.last.right = H2.first
H1.last = H2.last
return H1
else
H2.last.right = H1.first
H2.last = H1.last
return H2
Стоимость .
extractMin
Чтобы извлечь минимальный элемент из тонкой кучи нужно:
- Удалить корень с минимальным ключом из корневого списка.
- Уменьшить ранг для всех его тонких детей.
- Cлить детей с корневым списком.
- Объединять, пока возможно, тонкие деревья одного ранга.
Это можно сделать, например, с помощью вспомогательного массива размером , в -ой ячейке которого хранится корень тонкого дерева ранга .
Изначально массив пуст, а мы добавляем в него все деревья нашего корневого списка.
При добавлении нового дерева мы, если дерево такого ранга уже есть в массиве, связываем его с существующим и пытаемся добавить новое дерево с рангом на больше.
Node extractMin(H)
// Удаляем минимальный корень из корневого списка
tmp = H.first
H.first = H.first.right
if H.first == null H.last = null
// Снимаем тонкость с его детей и добавляем их в корневой список
x = tmp.first.child
while x != null
if isThin(x)
x.rank = x.rank - 1
x.left = null
next = x.right
insert(H, x)
x = next
// Объединяем все корни одного ранга с помощью вспомогательного массива aux
max = -1
x = H.first
while x != null
while aux[x.rank] != null
next = x.right
if aux[x.rank].key < x.key
swap(aux[x.rank], x)
aux[x.rank].right = x.child
x.child.left = aux[x.rank]
aux[x.rank].left = x
x.child = aux[x.rank]
aux[x.rank] = null
x.rank = x.rank + 1
aux[x.rank] = x
if x.rank > max
max = x.rank
x = next
// Собираем все корни обратно в тонкую кучу
H = makeHeap()
i = 0
while i <= max
insert(H, aux[i])
i = i + 1
return tmp
Пусть мы сделали связывающих шагов (linking steps) во время добавления в массив.
Мы удалили корень из списка за , затем за нормализовали детей корня и добавили в корневой список, далее за получили новый корневой список, в котором за нашли минимальный корень и подвесили список за него.
Получили фактическую стоимость . С другой стороны, при добавлении детей в список мы увеличили потенциал не более чем на , а каждый связывающий шаг уменьшает наш потенциал на . Отсюда стоимость .
Стоимость .
decreaseKey
После уменьшения ключа может быть нарушена кучеобразность, в этом случае мы переносим все поддерево с корнем в уменьшаемом элементе в корневой список, также обновляем минимум в тонкой куче.
Теперь могут быть нарушены свойства тонкого дерева, будем различать два вида нарушений:
- Братские нарушения — это нарушения третьего свойства тонкого дерева.
- Родительские нарушения — это нарушения первого или второго свойства тонкого дерева.
Назовем узел узлом локализации братского нарушения среди детей узла , если ранг узла отличается от ранга его ближайшего правого брата на 2, либо он не имеет правого брата и его ранг равен 1.
Назовем узел узлом локализации родительского нарушения, если выполнено одно из трех условий:
- Ранг узла на три больше, чем ранг его самого левого сына.
- Ранг узла равен двум, и он не имеет детей.
- Узел есть тонкий корень дерева.
Пусть узел — это узел локализации братского нарушения.
- Узел не тонкий, тогда помещаем поддерево с корнем в самом левом сыне узла на место пропущенного в братском списке. Узел становится тонким, дерево становится корректным, процедура исправления завершается.
- Узел тонкий, тогда уменьшаем ранг узла на единицу. Теперь узлом локализации нарушения будет либо левый брат узла , либо его родитель, тогда нарушение станет родительским.
С помощью этих действий мы избавились от братских нарушений, теперь разберем родительские.
Пусть узел — это узел локализации родительского нарушения, а узел — родитель узла .
Переместим все поддерево с корнем в в корневой список и уменьшим ранг .
- Узел не был тонким, пометим его как тонкий, тогда дерево станет корректным.
- Узел был тонким, тогда — новый узел локализации родительского нарушения, переходим к нему.
Продолжая эту процедуру, мы или остановимся, или дойдем до корня дерева, тогда достаточно сделать ранг корня на 1 больше ранга его самого левого сына.
Каждый промежуточный шаг рекурсии уменьшает количество тонких узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость .
Стоимость .
delete
Чтобы удалить элемент из тонкой кучи нужно сначала выполнить этого элемента до , а затем выполнить .
void delete(H, x)
decreaseKey(H, x, )
extractMin()
Стоимость .
