Приоритетная очередь

Алла: Ты упоминал про ещё один эффективный метод сортировки с помощью деревьев. Расскажешь подробнее?

Тимофей: Да, конечно! Ответь мне только сначала на вопрос.

Как хранятся деревья поиска в памяти?

В ячейках памяти, которые располагаются последовательно.

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

В ячейках памяти, которые располагаются произвольно.

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

Тимофей: Узлы дерева обычно хранятся в произвольных местах памяти. Поэтому можно эффективно добавлять и удалять элементы. Но есть другой способ представления деревьев — в виде массива. Такой способ используется при реализации структуры данных приоритетная очередь.

Вы уже знаете, что такое очередь. Она работает по принципу FIFO — “first in first out”. То есть первый добавленный элемент извлекают первым, а последний добавленный — последним.

Существует похожая структура данных приоритетная очередь (англ. priority queue) — это очередь, элементы которой имеют приоритет.

При посадке в самолёт сначала проходят пассажиры бизнес-класса, владельцы sky priority и пассажиры с детьми. Затем все остальные. То есть при посадке на борт некоторые пассажиры имеют приоритет.

Гоша: А если пилот придёт на посадку вместе с пассажирами?

Тимофей: Его пропустят на борт первым.

Алла: А если пассажир — президент?

Гоша: То, вероятно, пилот немного подождёт!

Тимофей: Также если пациент не записался на приём к врачу, ему придётся ждать, пока не зайдут все пациенты по записи. То есть у пациентов по записи приоритет выше.

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

Важное свойство приоритетной очереди — после вставки или удаления элемента, она остаётся в упорядоченном состоянии.

Первым из очереди всегда извлекается наиболее приоритетный элемент.

Гоша: Так как же устроена эта очередь? Почему из неё легко извлечь самый приоритетный элемент?

Тимофей: Чтобы это понять, разберём два новых понятия.

Полное бинарное дерево

T_h

высоты

h

— бинарное дерево, у которого путь от корня до любой вершины содержит ровно

h

рёбер. При этом у всех узлов дерева, которые не являются листьями, есть правый и левый потомок.

Бинарная куча — двоичное дерево, которое удовлетворяет условиям:

Значение в любой вершине не больше (если куча для минимума), чем значения её потомков.
На $i$ -ом слое $2^i$ вершин, кроме последнего. Для последнего слоя это условие может не выполняться. Слои нумеруются с нуля.
Последний слой заполнен слева направо.

Первое свойство гарантирует, что в вершине находится самый приоритетный элемент.

Другое название этой структуры данных — пирамида (англ. heap).

Верно ли, что все элементы в левом поддереве меньше корня?

Верно.

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

Не верно.

В начале урока мы говорили, что дерево можно хранить в массиве. Разберёмся, как это работает.

Рассмотрим приведённый выше пример для неубывающей пирамиды.

Пирамида будет храниться в массиве так:

Скопировать кодPYTHON
[3, 6, 5, 11, 23, 16, 9, 96, 17]

Благодаря структуре пирамиды по номеру дочернего узла можно определить номер его родителя, а по номеру родителя — индексы его потомков, если они существуют.

Индекс корня дерева всегда равен 1. Это отличается от стандартной нумерации массивов. В них индексация начинается с 0. Корень с индексом 1 упрощает формулы поиска остальных элементов. Рассмотрим их.

Индекс родителя узла $i$ равен $\left [\frac{i}{2} \right ]$ , где $[x]$ означает округление до ближайшего целого числа, которое меньше или равно $x$ .
Индекс левого потомка узла $i$ равен $2i$ .
Индекс правого потомка узла $i$ равен $2i+1$ .

Посмотрим на примере:

Определим индексы потомков для корня:

Индекс левого потомка

i

равен

2i

, то есть 2.

Индекс правого потомка

i

равен

2i+1

, то есть 3.

Всё верно!

Теперь определим родителя для узла с номером 5.

Индекс родителя узла

i

равен

\left [\frac{i}{2} \right ]

, то есть [2,5]. Округлим 2,5 до целого числа и получим 2.

Верно! Мы убедились в корректности формул.

Благодаря свойствам пирамиды нам не нужно хранить в памяти указатели на детей и родителей. Это существенно экономит память.

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

Добавим элемент в конец кучи:

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

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

Разберёмся, как это исправить.

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

В примере достаточно одной итерации и пирамида снова удовлетворяет своим свойствам.

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

Теперь извлечём самый приоритетный элемент из кучи.

Удаление элемента нарушило свойство упорядоченности бинарной кучи. Восстановим его. Функцию восстановления свойств пирамиды обычно называют heapify.

Рассмотрим текущий узел и его дочерние элементы.

Если текущий элемент — самый приоритетный из них, ничего не меняем.

Иначе меняем текущий элемент с максимальным приоритетным — он должен оказаться выше.

Мы поменяли местами вершину с левым потомком. Правую часть дерева не трогали, поэтому на следующем шаге рассматривать её не нужно. Проверим свойство упорядоченности в левой части дерева. Если нужно, скорректируем тем же алгоритмом.

Три элемента: 14, 17 и 45 расположены в неправильном порядке. 14 меньше 17 и 45.

Снова поменяем местами элемент в текущей вершине с максимальным.

У текущего элемента нет дочерних узлов. Значит, мы восстановили свойство бинарной кучи.

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

Если значение текущего узла больше, чем значение его потомков.
Если у текущего узла отсутствуют потомки.

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

Гоша: Немного сложно, но я опять понял! Так, а что по поводу сортировки?

Тимофей: Скоро всё узнаете!