Основные подходы к реализации очередей с приоритетом

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

Определим требуемые операции:

1) Вставка элемента

2) Извлечение самого приоритетного элемента

3) Получение значения самого приоритетного элемента

4) Изменение ключа элемента

5) Слияние очередей

Очереди с приоритетом можно реализовать при помощи массивов или списковых структур. Среди последних выбирают как связные списки, так и линейные абстрактный типы данных. Однако эти структуры данных не позволяют построить очереди с приоритетом, в которой все операции выполнялись бы быстрее, чем O(n). В тоже время такая реализация необходима при работе с большими объёмами данных. В таких случаях применяют структуры данных, отличные от линейных, например, основанные на сбалансированных деревьях, из которых особо известны бинарные кучи, биномиальные кучи, кучи Фибоначчи.

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

Бинарная куча

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

Рисунок 2.4 – Бинарная куча

 

Бинарную кучу обычно представляют и реализуют в виде массива. Такой выбор обусловлен тем, что куча сбалансирована, поэтому представление её как массива является тривиальной задачей. Хранение данных в виде массива, очевидно, экономнее, нежели в виде древовидной структуры. Применяется следующее правило для представления кучи в виде массива: если родительская вершина имеет индекс i, то её сыновья имеют индексы 2*i + 1 и 2*i + 2 соответственно (при индексации с нуля).

Тогда куча на рисунке выше будет выглядеть следующим образом

100 19 36 17 3 25 1 2 7

Для вставки в бинарную кучу применяют следующий механизм:

Помещаем вершину в конец массива, потом сравниваем с родителем. Если родитель менее приоритетный, меняемся с ним местами. Производим данную процедуру до тех пор, пока не восстановим свойства кучи. Этот механизм называется просеивание вверх.

В качестве примера вставим в кучу вершину 43

100 19 36 17 3 25 1 2 7 43 = 100 19 36 17 43 25 1 2 7 3 = 100 43 36 17 19 25 1 2 7 3

Для изменения ключа модифицируем его значение на нужное, после чего при помощи просеивания восстанавливаем свойства кучи. Например, поменяем значение ключа 100 на 14

14 43 36 17 19 25 1 2 7 3 = 43 14 36 17 19 25 1 2 7 3 = 43 25 36 17 19 14 1 2 7 3

Для удаления ключа заменим первый элемент последним, после чего восстановим свойства кучи. Пример:

43 25 36 17 19 14 1 2 7 3 = 3 25 36 17 19 14 1 2 7 = 36 25 3 17 19 14 1 2 7 = 36 25 14 17 19 3 1 2 7

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

Следующая куча, которая будет рассмотрена, имеет эффективный алгоритм объединения.

 

 

Биномиальная куча

Биномиальная куча - это множество биномиальных деревьев, каждое из которых удовлетворяет свойству кучи (рисунок 2.6).

Биномиальное дерево — это дерево, определяемое по индукции:

B₀ – дерево, состоящее из одного узла.

B_i – дерево, состоящее из двух биномиальных деревьев B_i-1

Если рассмотреть дерево степени n, то на i уровне будет вершин. Обычно биномиальные деревья представляются в виде корневого списка в порядке возрастания степеней (Рисунок 2.5)

Рисунок 2.5: Пример биномиальных деревьев

Рисунок 2.6: Пример биномиальной кучи

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

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

Пример сложения степеней:

1-2-3-5 + 2-3-4 = 1-2-2-3-3-4-5 = 1-3-3-3-4-5 = 1-3-4-4-5 = 1-3-5-5 = 1-3-6

Данная операция корректна, так как согласно структуре Бинома Ньютона дерево степени n имеет 2ⁿ вершин, а 2ⁿ + 2ⁿ = 2ⁿ⁺¹

Таким образом добавление элемента в кучу можно определить, как слияние текущей кучи с кучей из одного элемента (куча степени 0)

Для удаления из кучи приоритетного элемента необходимо сперва найти такой элемент, затем удалить из дерева корневой элемент. В результате дерево степени n распадется на деревья степеней 0,1.. n-1. Доказать этот факт можно при помощи тождества

2ⁿ – 1 = 2^n-1 + 2^n-1 – 1

2^n-1 – 1 = 2^n-2 + 2^n-2 – 1.

…

2¹ – 1 = 2⁰ + 2⁰ – 1 = 2⁰

Значит 2ⁿ -1 =

Для уменьшения ключа присваиваем ему новое значение, после чего при помощи просеивания поднимаем его вверх до тех пор, пока не восстановим свойства кучи.

Биномиальная куча дает логарифмическое время для всех основных операций. Однако не смотря на это данная куча не очень популярна. Это вызвано тем, что существуют кучи, которые работают быстрее при тех же затратах памяти (Бинарная куча, например, используется благодаря экономному расходу памяти, простоты реализации, и представления). Следующая куча, которая будет рассмотрена, является модернизированной версии биномиальной кучи, и ускоряет скорость работы некоторых операция до константных.

 

 

Куча Фибоначчи

Фибоначчиева куча — набор деревьев Фибоначчи, корни которых объединены в неупорядоченный циклический двусвязный список. В отличие от биномиальной кучи, степени корней не обязаны быть попарно различными (Рисунок 2.8)

Дерево Фибоначчи - биномиальное дерево, где у каждой вершины удалено не более одного ребенка (Рисунок 2.7)

Рисунок 2.7: Дерево Фибоначчи высоты 4

 

Рисунок 2.8: Куча Фибоначчи

 

Вставка в кучу подразумевает добавление в список дерева степени 0 (дерево из одной вершины). Таким образом куча вырождается в список (Рисунок 2.9).

 

Рисунок 2.9: Вырожденная куча из 10 элементов

 

Объединение двух куч заключается в связывании крайних элементов двух куч. (Рисунок 2.10)

Рисунок 2.10: Добавления к исходной куче кучи 12-13-11

Для удаления из кучи вершины изменим ее значение ключа на - , и затем, чтобы восстановить свойства кучи просеем её к корневому списку. Если у удаляемой вершины есть дети, помещаем их к корневому списку. Далее начинается балансировка кучи, которая выполняется только при удалении, и нужна для того, чтобы куча не был вырождена в список. Суть балансировки заключается в следующем: берем две вершины степени n и объединяем их в дерево степени n+1, при этом в корне будет самый приоритетный из элементов, а менее приоритетный станет сыном. (Рисунок 2.11)

Рисунок 2.11: Куча после удаления элемента с ключом 11

 

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

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

Преимущества кучи Фибоначчи над биномиальной в том, что операции, не требующие удаления, работают за константное время, а те что требуют удаления – за логарифмическое.

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

Были рассмотрены основные подходы к реализации очередей с приоритетом. Вопросом оптимизации куч Фибоначчи, направленных на уменьшение скрытой константы занялся Tadao Takaoka, который в своей работе Theory of 2-3 Heaps описал структуру данных, которая способна решить данную проблему.

 

 

СТРУКТУРА ДАННЫХ 2-3 КУЧА

Основная проблема куч Фибоначчи заключалась в том, что балансировка кучи происходит только при удалении из кучи. Если бы мы смогли реализовать структуру данных, которая будет сохранять балансировку и при добавлении в кучу(слиянии), но при этом сохранив асимптотику, то удалось бы получить выигрыш в производительности. И эта структура – 2-3 куча.

2-3 куча — это массив 2-3 деревьев, определенных по индукции:

B₀ дерево состоит из одного или двух элементов

B_i дерево, состоит из B_i* + B_i-1

B_i* дерево, состоящее из B_i-1 + B_i-1 (Рисунок 3.1).

 

Рисунок 3.1: дерево 2-3 кучи

 

2-3 дерево - это сбалансированное дерево, родительский узел которого может иметь как два, так и три сына (Рисунок 3.2). 2-3 деревья относятся к деревьям и являются идеально сбалансированными. Высота дерева из n вершин лежит в диапазоне [ ] Однако 2-3 деревья из-за своей структуры занимают много памяти, так как фактическая информация храниться только в листьях, а узлы используются для адресации на нужный лист. В целях экономии произведем модификацию: Будем хранить данные по тому же принципу, что и в бинарных деревьях. Мы сможем себе это позволить в том случае если условимся объединять только деревья одной степени, что нам в принципе и надо.

На рисунках 7.1 и 7.2 приведен пример 2-3 дерева, и 2-3 дерева кучи:

 

Рисунок 3.2: 2-3 дерево

Раз мы ограничились в слиянии только деревьев одной степени, необходимо их классифицировать, и для этого введем два понятия:

Степень дерева– высота корневого узла

Насыщенность дерева– Наличие у корневого элемента партнерской связи (подробнее при описании структуры узла).

По насыщенности будем различать: насыщенные(t) и ненасыщенные(f) деревья. Тогда в куче будем xранить деревья по следующему принципу: в i ячейке дерева можно хранить только дерево степени i.

Как говорилось ранее дерево степени 0 содержит в себе или 1, или 2 вершины. Тогда в случае если дерево хранит 1 вершину, это ненасыщенное дерево степени 0(0f), а если 2 вершины, то это насыщенное дерево степени 0(0t). Насыщенное дерево при добавлении к нему вершин переходит в ненасыщенное более высокой степени. Дерево степени 1 будет хранить 3 или 6 вершин соответственно. Тогда насыщенное дерево степени n будет хранить в себе 3ⁿ вершин, а ненасыщенное 3ⁿ+3ⁿ = 2*3ⁿ вершин.

Таким образом насыщенное дерево является объединением двух ненасыщенных деревьев. Тогда максимальное количество элементов в куче из n деревьев выражается как . Примеры некоторых деревьев:

 

Таблица 2: Пример деревьев 2-3 кучи

Теперь самое время затронуть детали реализации и описать структуру узла 2-3 кучи (Рисунок 3.3):

Рисунок 3.3: Структура узла 2-3 кучи на примере 1f дерева

Где:

K (key) – ключ, определяет приоритет элемента

V (value) – значение, которое храниться вместе с ключом

pr (parent) – родительский узел, элемент с более высоким приоритетом

сh(child) – дочерний узел, элемент с более низким приоритетом

pt (partner) – партнерский узел. При объединении двух f деревьев они соединяются как партнеры. При этом узлы, подчиненные одному из партнеров непосредственно с другим партнером связей не имеют. Также имеет место нюанс: необходимо как-то помечать того партнера, который является более приоритетным. Во-первых, это позволит избежать лишних проверок при выполнении всех основных операций, во-вторых поможет избежать проблем при обходе кучи, в-третьих если партнер будет являться сыном, мы сразу будем знать по какому из них нужно возвращаться к родителю, и при этом ссылку на родителя у менее приоритетного элемента хранить не обязательно. Будем помечать самого приоритетного из двух соседей флагом sl(sister in law).Также для корневого элемента эта метка будет определять факт насыщенности дерева.

ln(left neighbor) – левый сосед

rn(right neighbor) – правый сосед

Необходимость соседской связи, и особенность реализации будет обозначена при описании алгоритма вставки.

 

 

Вставка в кучу

 

Теперь рассмотрим основные операции над кучей, и начнем с операции вставки. Операция вставки определяется как слияние исходной кучи с кучей из одного дерева (если вставляем один элемент, то дерева 0f). В куче не может существовать два дерева одинаковой степени, поэтому пря появлении таковых мы будем их объединять до тех пор, пока все степени не будут различны. Может возникнуть две ситуации при слиянии куч: В самом простом случае при добавлении в кучу дерева может оказаться, что ячейка массива свободна, тогда просто занимаем её. В противном случае, если ячейка уже занята, будем производить слияние. (Рисунок 3.4)

Рисунок 3.4: Схема вставки в кучу

 

Слияние через партнера возникает, когда оба дерева ненасыщенные. В таком случае, раз оба дерева не имеют партнера, для объединения их достаточно просто связать их как партнеров. Операцию можно выразить формулой: nf + nf = nt (Рисунок 3.5)

Рисунок 3.5: Вставка через партнера

 

Слияние через сына выглядит несколько сложнее. В самом примитивном варианте, когда деревья степени 0, это выглядит так: из двух корневых элементов выбирается самый приоритетный (в случае если он из насыщенного дерева, мы его меняем местами с корневым элементом из ненасыщенного дерева), к нему добавляет насыщенное дерево как сына. При этом, раз степень дерева увеличилась, его необходимо вставлять заново (так как n+1 ячейка может быть занята). Общая формула: nf + nt = (n+1)f

Рисунок 3.6: Вставка через сына

 

Но тут возникает одна проблема, а что если деревья не нулевой степени (у каждого из деревьев уже есть сын)? В этом случае нам и пригодиться соседская связь. Мы отделяем сына от самого приоритетного элемента, и добавляем его как соседа к самому приоритетному из насыщенного дерева (помеченное как sl). Данная манипуляция представлена на рисунке 3.7 (на примерах 1f + 1t = 2f и 2f+2t = 3f):

Рисунок 3.7: Пример использования соседской связи

 

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

Например, для 3f дерева из примера выше самая верхняя соседская связь будет выглядеть так:

10 8 3 10. На схеме эти ссылки не указывались, во-первых, чтобы не усложнять рисунок, во-вторых наличие таких связей не обязательно, а лишь элемент моей реализации, который оптимизирует некоторые операции, например, это упрощает рекурсию при обходе кучи, а наличие обратной связи и вовсе позволяет заменить рекурсию циклом в операции изменения ключа. Ещё несколько моментов, связанных с моей реализацией: если необходимо вставить не одно дерево, а несколько, деревья подаются не как массив, а как одно дерево. Для этого все деревья связываются через корневые вершины как соседи. Так как соседская связь корневой вершины всегда не занята, эта манипуляция допустима. Если дерево не имеет соседей, то указатели ссылаются не на NULL, а на само дерево. Благодаря этому становиться проще формировать кольцевые списки соседей.

Существует ещё одна разновидность слияния – делением. Деление применяется в том случае, когда необходимо объединить две насыщенные вершины. При операции вставки не существует такой ситуации, при которой эта операция необходима, однако, данная операция имеет место при удалении. Опишем алгоритм вставки в кучу делением.

Из двух корневых вершин выберем самую приоритетную, и отделим от соседней. Отделенную вершину будем объединять через сына с насыщенным деревом. Таким образом если мы имели два дерева nt, на выходе будем иметь nf + (n+1) f. После этих манипуляций nf дерево оставляем лежать в ячейке, а (n+1) f вставляем заново.

Рисунок 3.8: Вставка Делением

Рисунок 3.9: Пример слияния 2t + 2t = 2f 3f

 

Теперь, когда все операции рассмотрены, самое время поговорить о реализации. Вставка будет разделена на два блока: интерфейс вставки и слияние. Интерфейс вставки будет отвечать за выборку двух сливаемых деревьев (вставляемое дерево + дерево, занимающее позицию), и обработку результата модуля слияния. В случае, когда позиция свободна модуль будет размещать дерево в нужной ячейке, в обратном же случае он будет отдавать управление модулю слияния. Модуль слияния отвечает за выбор алгоритма слияния, и приведение его в исполнение. На выход будут отдаваться ссылки на вставленное дерево (если нету, то NULL), и дерево, которое необходимо вставить (если нету, то NULL). Второй случай возникает тогда, когда в результате слияния степень дерева изменилась. Вставка через партнера возвращает вставленное дерево. Вставка через сына возвращает дерево, которое необходимо вставить. Вставка слиянием возвращает два дерева.

Вставка не зависит от количества элементов в куче, а зависит от количества деревьев. Но поскольку количество деревьев в куче в данный момент времени не зависит от количества элементов, то операция вставки не зависит от размера кучи, следовательно, операция работает за O(1).