Очереди по приоритетам и пирамидальная сортировка

Во многих приложениях требуется обработка записей с упорядоченными определенным образом ключами, но не обязательно в строгом порядке и не обязательно все сразу. Часто мы накапливаем некоторый набор записей, после чего обрабатываем запись с максимальным значением ключа, затем, возможно, накопление записей продолжается, потом обрабатывается запись с наибольшим текущим ключом и т.д. Соответствующая структура данных в подобного рода средах поддерживает операции вставки нового элемента и удаления наибольшего элемента. Такая структура данных называется очередью по приоритетам. Использование очереди по приоритетам подобно использованию обычных очередей (удаляется самый старый элемент) и стеков (удаляется самый новый элемент), однако их эффективная реализация представляет собой довольно трудную задачу. Очередь по приоритетам является наиболее важным примером обобщенного абстрактного типа данных (АТД), которые обсуждались в разделе 4.6. Фактически, очередь по приоритетам представляет собой оправданное обобщение стека и очереди, поскольку эти структуры данных можно реализовать посредством очередей по приоритетам, используя соответствующий механизм установки приоритетов (см. упражнения 9.3 и 9.4).

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

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

Любую очередь по приоритетам можно использовать как основу для алгоритма сортировки, устанавливая все записи в очередь, а затем последовательно исключая из нее наибольшие текущие записи, чтобы получить последовательность записей в обратном порядке. Далее в книге будет показано, как следует использовать очередь по приоритетам в качестве строительных блоков для более совершенных алгоритмов. В части 5 мы разработаем алгоритм сжатия файлов, использующий программы из данной главы, в главе 7 увидим, как очереди по приоритетам могут служить подходящими абстракциями для упрощения понимания взаимоотношений между множеством фундаментальных алгоритмов поиска в графах. Здесь упомянуто всего лишь несколько примеров той важной роли, которую играют очереди по приоритетам как базовые инструментальные средства при разработке алгоритмов.

На практике очереди по приоритетам намного сложнее, чем это следует из только что сформулированного простого определения, поскольку существуют несколько других операций, которые могут потребоваться для поддержки очередей при всех условиях, которые могут возникнуть во время их использования. И в самом деле, одна из основных причин того, что многие реализации очереди с приоритетами находят широкое практическое применение, заключается в их гибкости, позволяющей клиентским программам выполнять различные операции над наборами записей с ключами. Необходимо построить и поддерживать структуры данных, содержащие записи с числовыми ключами {приоритетами), которые поддерживают некоторые из следующих операций:

Создать (construct) очередь по приоритетам из N заданных элементов,

Вставить (insert) новый элемент,

Удалить наибольший (remove the maximum) элемент,

Изменить приоритет (change the priority) произвольно выбранного элемента,

Удалить (remove) произвольно выбранный элемент,

Объединить (join) две очереди но приоритетам в одну.

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

Имеются области, в которых эти операции взаимно перекрываются, а в некоторых случаях удобно дать определения других, подобных операций. Например, у некоторых клиентских профамм часто возникает необходимость найти наибольший (find the maximum) элемент в очереди по приоритетам без его удаления из очереди. Или же

понадобится операция заменить наибольший (replace the maximum) элемент новым элементом. Мы можем реализовать подобного рода операции за счет использования в качестве строительных блоков две базовых операции: операцию найти наибольший можно представить через операцию удалить наибольший и следующую за ней операцию вставить, а операцию заменить наибольший можно представить либо через операцию вставить и следующую за ней удалить наибольший, либо через операцию удалить наибольший и следующую за ней вставить. Однако более эффективный программный код обычно получается за счет реализации таких операций непосредственно, при условии, что в них существует потребность и существует их точное описание. Точное описание не всегда однозначно, как это может показаться на первый взгляд. Например, только что сформулированные два варианта операции заменить наибольший (replace the maximum) существенно отличаются друг от друга: первый из них приводит к тому, что размер очереди временно увеличивается на один элемент, а во втором в очередь каждый раз вставляется новый элемент. Аналогично, операция изменить приоритет может быть реализована как удалить с последующей операцией вставить, а операция построить может быть реализована как многократное применение операции вставить.

Для некоторых приложений более удобным может оказаться поменять ориентацию на обратную и работать с наименьщими элементами, а не с наибольщими. Мы предпочитаем работать, главным образом, с очередями по приоритетам, которые настроены на доступ к наибольшим ключам, а не к наименьшим. Когда потребуется противоположная ориентация, мы будем называть ее (т.е. очередь по приоритетам, которая позволит удалять наименьший элемент (remove the minimum)) очередью по приоритетам, ориентированной на минимальный элемент (minimum-oriented).

Программа 9.1. Базовый тип абстрактных данных очереди по приоритетам

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

template <class Item> class PQ {

private

Программный код, который зависит от реализации public:

PQ(int) ;

int enrptyO const; void insert(Item); Item getmaxO ;