[Из песочницы] Структуры данных: 2-3 куча (2-3 heap)

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

В компьютерных науках для эффективной реализации очереди с приоритетом используются структуры в виде кучи.



Куча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких как алгоритм Дейкстры и сортировка методом пирамиды.

Одними из наиболее изученных и хорошо зарекомендовавших себя структур данных для хранения и работой с очередью с приоритетом являются Бинарная Куча (Binary Heap) и Куча Фибоначчи (Fibonacci Heap). Но данные структуры обладают некоторыми особенностями.

Например, бинарная куча для основных операций имеет трудоемкость Θ(logn), кроме нахождения минимального, а для слияния таких куч потребуется линейное время (!). Зато для хранения такой кучи необходимо мало памяти по сравнению с другими кучами.

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

Решением над этой проблемой занялся Тадао Такаока (Tadao Takaoka), опубликовав свою работу «2-3 heap» в 1999 году…

Немного о структуре «2-3 Heap»

2-3 куча (2-3 heap) — это структура данных типа дерево, которая удовлетворяет свойству кучи (min-heap, max-heap). Является альтернативой кучи Фибоначчи (Fibonacci heap). Состоит из 2-3 деревьев.

Решение, которое предлагает 2-3 heap, заключается в том, что в отличии от Кучи Фибоначчи, 2-3 куча выполняет балансировку не только при удалении, но и при добавлении новых элементов, снижая вычислительную нагрузку при извлечении минимального узла из кучи.

Количество детей вершины t произвольного дерева T назовем степенью (degree) этой вершины, а степенью дерева назовем степень его корня.

2-3 деревьями называются деревья T₀, T₁, T₂, ..., определенные индуктивно. Дерево T₀ состоит из единственной вершины. Под деревом T_i понимается дерево, составленное либо из двух деревьев T_i-1 либо из трех: при этом корень каждого следующего становится самым правым ребенком корня предыдущего.

Деревьями 2-3 кучи назовем деревья H[i]. Дерево H[i] — это либо пустое 2-3 дерево, либо одно, либо два 2-3 дерева степени i, соединенные аналогично деревьям T_i.

2-3 куча – это массив деревьев H[i] (i=0..n), для каждого из которых выполняется свойство кучи.

рис. Визуальное представление кучи

Структура узла

Каждый узел имеет указатели на другие узлы (поля имеющие стрелки), служебные поля и пара ключ (приоритет) – значение.

Основные операции

Поиск минимального в 2-3 heap (FindMin)

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

Поддерживая указатель на минимальный узел в куче мы можем находить этот узел за константное время ( Θ(1) )

Вставка в 2-3 heap (Insert)

1. Для добавления нового элемента создадим дерево H[0] содержащее одну вершину


2. Произведем операцию добавления этого дерева в кучу. При добавлении дерева степени i в кучу возможны следующие варианты:
   
   
   
   
   1. Если дерева с таким приоритетом нет, то просто его добавляем в кучу.
   
   
   2. Иначе извлекаем такое дерево из кучи и соединяем с добавляемым, после добавляем полученное дерево в кучу
   
   
   
   


3. После добавление поправляем указатель на минимальный корень

рис. Анимация последовательного добавления элементов в 2-3 кучу

Удаление минимального элемента из кучи

Минимальный элемент кучи находится в корне одного из деревьев кучи, допустим в H[i] – найдем его с помощью FindMin. Извлечем дерево H[i] из кучи и удалим его корень, при этом дерево распадется на поддеревья, которые мы впоследствии добавим в кучу.

Будем удалять корень рекурсивно: если дерево состоит из одной вершины, то просто удалим её; иначе отсоединяем от корня самого правого ребенка и продолжим удаление.

Уменьшение ключа у элемента

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

Объединение двух куч в одну

Имеется две кучи, которые нужно объединить в одну. Для этого мы будем по очереди извлекаем все 2-3 деревья из второй кучи и вставлять их в первую кучу. После нужно будет поправить счетчик количества узлов: суммируем количество элементов в первой и во второй куче и записываем результат в счетчик в первой куче, а во второй куче устанавливаем счетчик в 0.

Сравнение трудоемкостей операций с другими алгоритмами

В таблице приведены трудоемкости операций очереди с приоритетом (в худшем случае, worst case)

Символом ‘*’ отмечена амортизированная сложность операций

Операция	Binary Heap	Binomial Heap	Fibonacci Heap	2-3 Heap
FindMin	Θ(1)	O(logn)	Θ(1)*	Θ(1)*
DeleteMin	Θ(logn)	Θ(logn)	O(logn)*	O(logn)*
Insert	Θ(logn)	O(logn)	Θ(1)*	Θ(1)*
DecreaseKey	Θ(logn)	Θ(logn)	Θ(1)*	Θ(1)*
Merge/Union	Θ(n)	Ω(logn)	Θ(1)	Θ(1)*

Спасибо за уделенное внимание!

Исходный код реализации на C++, основанной на статье автора 2-3 Heap доступен на GitHub под MIT.

PS: При написании курсового проекта по этой теме, я понял, что информации в Рунете практически нет, поэтому решил внести свои пару копеек в это дело, рассказав заинтересованному сообществу об этом алгоритме.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Want something else to read? How about 'Grievous Censorship' By The Guardian: Israel, Gaza And The Termination Of Nafeez Ahmed's Blog