Тонкая куча
Тонкая куча — это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и фибоначчиева куча, но имеющая большую практическую ценность из-за меньших констант.
Тонкие кучи, как и многие другие кучеобразные структуры, аналогичны биномиальным кучам.
Тонкое дерево
Определение: |
Тонкое дерево (thin tree) биномиального дерева удалением самого левого сына у нескольких внутренних, то есть не являющихся корнем или листом, узлов. | ранга — это дерево, которое может быть получено из
Ограничение на принадлежность внутренним узлам вызвано тем, что у листьев детей нет, а если у корня удалить самого левого сына, то превратится в .
Утверждение: |
Ранг тонкого дерева равен количеству детей его корня. |
Для любого узла
в дереве обозначим:- — количество детей узла .
- биномиальном дереве . — ранг соответствующего узла в
Свойства тонкого дерева
Утверждение: |
Тонкое дерево обладает следующими свойствами:
|
![](/wiki/images/8/83/Thin_trees.png)
Тонкая куча
Определение: |
Тонкий лес (thin forest) — это набор тонких деревьев, ранги которых не обязательно попарно различны. |
Утверждение: |
Для любого натурального числа существует тонкий лес, который содержит ровно элементов и состоит из тонких деревьев попарно различных рангов. |
Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо. |
Определение: |
Тонкая куча (thin heap) — это кучеобразно нагруженный тонкий лес, то есть каждое тонкое дерево удовлетворяет условиям кучи. |
Пусть — максимально возможный ранг узла в тонкой куче, содержащей элементов.
Теорема (О максимальном ранге узла): |
В тонкой куче из элементов , где — золотое сечение. |
Доказательство: |
Сначала покажем, что узел ранга в тонком дереве имеет не менее потомков, включая самого себя, где — -е число Фибоначчи.Действительно, пусть — минимально возможное число узлов, включая самого себя, в тонком дереве ранга . По свойствам и тонкого дерева получаем следующие соотношения:для Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что хорошо известно. для любых . НеравенствоТеперь убедимся в том, что максимально возможный ранг тонкого дерева в тонкой куче, содержащей элементов, не превосходит числа .Действительно, выберем в тонкой куче дерево максимального ранга. Пусть Отсюда следует, что — количество вершин в этом дереве, тогда . . |
Представление тонкой кучи
Тонкую кучу можно представить как односвязный список корней тонких деревьев, причем корень с минимальным ключом должен быть первым в списке.
Поскольку при работе с тонкой кучей ссылка на родителя требуется только у самого левого его ребенка, можно хранить ее вместо ссылки на левого брата этой вершины.
Таким образом, для эффективной работы тонкой кучи необходимы следующие поля узла:
- — ключ (вес) элемента;
- — указатель на самого левого ребенка узла;
- — указатель на правого брата узла, либо на следующий корень, если текущий узел корень;
- — указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это корень;
- — ранг узла (количество дочерних узлов данного узла).
Для ускорения проверки на тонкость (thinness) можно отдельно хранить помеченность вершины. Также в вершине можно хранить любую дополнительную информацию.
Для работы с тонкой кучей достаточно иметь односвязный список ее корней.
Операции над тонкой кучей
Рассмотрим операции, которые можно производить над тонкой кучей. Время работы указано в таблице:
Многие операции над тонкой кучей выполняются так же, как и над фиббоначиевой.
Для амортизационного анализа операций применим метод потенциалов.
Пусть функция потенциала определена как
где — это количество тонких деревьев в куче, а — это количество помеченных вершин.Утверждение: |
Определённый таким образом потенциал обладает свойствами:
|
makeHeap
Для создания новой пустой тонкой кучи нужно вернуть ссылку на новый пустой корневой список, его потенциал
.
function ThinHeap makeHeap(); return null;
Стоимость
.insert
Для вставки элемента в тонкую кучу нужно создать новое тонкое дерево из единственного узла с ключом
, добавить его в корневой список на первое место, если этот ключ минимален, иначе на второе. Потенциал увеличивается на 1.Стоимость
.getMin
Для обращения к минимальному элементу в тонкой куче нужно обратиться к первому корневому узлу списка и вернуть его ключ, потенциал
не меняется.Стоимость
.meld
Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал
не меняется.Стоимость
.extractMin
Чтобы извлечь минимальный элемент из тонкой кучи нужно:
- Удалить корень с минимальным ключом из корневого списка.
- Уменьшить ранг для всех его помеченных детей.
- Cлить детей с корневым списком.
- Объединять, пока возможно, тонкие деревья одного ранга.
Это можно сделать, например, с помощью вспомогательного массива размером
, в -ой ячейке которого хранится корень тонкого дерева ранга .Изначально массив пуст, а мы добавляем в него все деревья нашего корневого списка.
При добавлении нового дерева мы, если дерево такого ранга уже есть в массиве, связываем его с существующим и пытаемся добавить новое дерево с рангом на
больше.Пусть мы сделали
связывающих шагов (linking steps) во время добавления в массив.Мы удалили корень из списка за
, затем за нормализовали детей корня и добавили в корневой список, далее за получили новый корневой список, в котором за нашли минимальный корень и подвесили список за него.Получили фактическую стоимость
. С другой стороны, при добавлении детей в список мы увеличили потенциал не более чем на , а каждый связывающий шаг уменьшает наш потенциал на .Cтоимость
.decreaseKey
После уменьшения ключа может быть нарушена кучеобразность, в этом случае мы переносим все поддерево с корнем в уменьшаемом элементе в корневой список, также обновляем минимум в тонкой куче.
Теперь могут быть нарушены свойства тонкого дерева, будем различать два вида нарушений:
- Братские нарушения — это нарушения третьего свойства тонкого дерева.
- Родительские нарушения — это нарушения первого или второго свойства тонкого дерева.
Назовем узел
узлом локализации братского нарушения среди детей узла , если ранг узла отличается от ранга его ближайшего правого брата на 2, либо он не имеет правого брата и его ранг равен 1.Назовем узел
узлом локализации родительского нарушения, если выполнено одно из трех условий:- Ранг узла на три больше, чем ранг его самого левого сына.
- Ранг узла равен двум, и он не имеет детей.
- Узел есть помеченный корень дерева.
Пусть узел
— это узел локализации братского нарушения.- Узел не помечен, тогда помещаем поддерево с корнем в самом левом сыне узла на место пропущенного в братском списке. Узел становится помеченным, дерево становится корректным, процедура исправления завершается.
- Узел помечен, тогда уменьшаем ранг узла на единицу. Теперь узлом локализации нарушения будет либо левый брат узла , либо его родитель, тогда нарушение станет родительским.
С помощью этих действий мы избавились от братских нарушений, теперь разберем родительские.
Пусть узел
— это узел локализации родительского нарушения, а узел — родитель узла .Переместим все поддерево с корнем в
в корневой список и уменьшим ранг .- Узел не был помечен, пометим его, тогда дерево станет корректным.
- Узел был помечен, тогда — новый узел локализации родительского нарушения, переходим к нему.
Продолжая эту процедуру, мы или остановимся, или дойдем до корня дерева, тогда достаточно сделать ранг корня на 1 больше ранга его самого левого сына.
Каждый промежуточный шаг рекурсии уменьшает количество помеченных узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость
.Стоимость
.delete
Чтобы удалить элемент из тонкой кучи нужно сначала выполнить
этого элемента до , а затем выполнить .Стоимость
.