Очередь с приоритетами

Общие сведения

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

• Каждому элементу очереди с приоритетами сопоставлено некоторое значение, именуемое приоритетом этого элемента. Приоритеты допускают сравнение друг с другом;
• Функция извлечения из очереди с приоритетами возвращает тот элемент, приоритет которого является максимальным.

Учащийся, выполняющий домашнее задание по нескольким предметам, может вводить различные показатели, определяющие порядок выполнения: от более любимых предметов к менее любимым, от менее сложных к более сложным, и так далее. Пожарная блигада планирует выезды сообразно с категорией сложности возгорания. Операционная система компьютера выделяет аппаратные ресурсы в первую очередь приложениям, запущенным с приоритетом реального времени, и лишь затем — остальным приложениям. Эти примеры позволяют пояснить назначение и принципы функционирования очередей с приоритетами.

Интерфейс

Интерфейс очереди с приоритетами в целом аналогичен интерфейсу обычной очереди, но в операции добавления появляется второй аргумент, а операция удаления возвращает элемент с наибольшим приоритетом:

void enqueue(T1 value, T2 priority)	— вставка элемента value с приоритетом priority в очередь;
T1 dequeue()	— извлечение элемента с максимальным приоритетом из очереди;
bool isEmpty()	— проверка очереди на отсутствие элементов.

Демонстрация работы

Демонстрация работы очереди с приоритетами

Реализация

Очередь с приоритетами, построенная на обычном контейнере (массиве или списке), позволяет выполнять вставку за O(1), но поиск и удаление элемента с максимальным приоритетом будут иметь сложность O(N). Существует более быстрая реализация очереди с приоритетами, подразумевающая применение особого способа организации данных, получившего название пирамиды (англ. heap, также используется термин «куча»; не следует путать с динамическим хранилищем данных в памяти, которое также именуется кучей).

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

Пирамиду можно построить на массиве, используя соотношения межу индексами ячеек массива для определения связей элементов. На рисунке ниже показан пример пирамиды, содержащей 8 элементов, и её отображение на массив.

Если индексация элементов массива начинается с единицы, то непосредственные потомки элемента с индексом i будут иметь индексы (2 * i) и (2 * i + 1), а родителем будет являться элемент с индексом (i / 2). Так, потомками элемента с индексом 1 будут элементы с индексами 2 и 3, потомками элемента с индексом 2 — элементы с индексами 4 и 5, родителем элемента с индексом 8 будет элемент с индексом 4.

Если индексация элементов массива начинается с нуля, то непосредственные потомки элемента с индексом i будут иметь индексы (2 * i + 1) и (2 * i + 2), а родителем будет являться элемент с индексом ((i + 1) / 2 - 1). Так, потомками элемента с индексом 0 будут элементы с индексами 1 и 2, потомками элемента с индексом 1 — элементы с индексами 3 и 4, родителем элемента с индексом 7 будет элемент с индексом 3.

Пирамида является почти полным двоичным деревом: только самый нижний уровень может быть не заполнен полностью, и его заполнение происходит строго слева направо. Можно показать, что в N-элементной пирамиде ⌈N/2⌉ последних элементов являются листьями, то есть не имеют потомков. При индексации массива с единицы листья имеют индексы от (N / 2 + 1) до N, при индексации с нуля — от (N / 2) до (N - 1).

Высотой пирамиды называется количество рёбер на самом длинном пути от вершины пирамиды до какого-либо листа. Достаточно легко убедиться, что высота пирамиды из N элементов равна ⌊log2N⌋.