Эта очередь по приоритетами суть прототипный АТД (см. главу 4): он представляет четко определенный набор операций над данными и является удобным абстрактным понятием, которое позволяет отделять прикладные программы (клиенты) от различных приложений, которые предстоит рассмотреть в настоящей главе. Интерфейс, заданный программой 9.1, определяет большую часть базовых операций над очередью по приоритетам; более полный интерфейс рассматривается далее в разделе 9.5. Строго говоря, различные подмножества различных операций, которые мы предпочтем включить в свой рабочий набор, приводит к различным абстрактным структурам данных, но для очередей по приоритетам наиболее характерными являются операции удалить наибольший (remove-the-maximum) и вставить (insert), поэтому им и будет уделяться основное внимание.

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

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

Далее, в разделах 9.2-9.4 внимание сосредоточивается на рассмотрении классической структуры данных, получившей название сортирующее дерево (heap), которая обеспечивает эффективную реализацию всех операций, кроме операции объединить. Кроме того, в разделе 9.4 исследуется важный алгоритм сортировки, который естественным образом вытекает из этих реализаций. После этого мы более подробно проанализируем некоторые проблемы, связанные с разработкой полных АТД очереди по приоритетам, в разделах 9.5 и 9.6. И в заверщение, в разделе 9.7 рассматриваются более сложные структуры данных, получившие название биномиальных очередей (binomial queue), которые используются для реализации всех операций (в том числе и операции объединить) в наихудшем случае логарифмической зависимости времени выполнения.

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

Упражнения

> 9.1. Буква означает операцию вставить, а звездочка - операцию удалить наибольший элемент из последовательности PRIO*R**I*T*Y***QUE***U*E.

Дать последовательность значений, возвращаемых операциями возвратить наибольший элемент.

> 9.2. Добавить к условиям упражнения 9.1 знак плюс, означающий операцию объединить, и круглые скобки для ограничения пределов очереди по приоритетам, построенной операциями, заключенными в эти скобки. Показать содержимое очереди по приоритетам, соответствующее последовательности

(((PRIO)+(R*IT*Y*))***) + (QUE***U*E).

о 9.3. Объяснить, как использовать АТД очереди по приоритетам для реализации АТД стека.

о 9.4. Объяснить, как использовать АТД очереди по приоритетам для реализации АТД очереди.

9.1. Элементарные реализации

Базовые структуры данных, которые обсуждались в главе 3, предоставляют множество различных возможностей для реализации очередей по приоритетам. Программа 9.2 демонстрирует реализацию, которая в качестве базовой структуры данных использует неупорядоченный массив. Операция найти наибольший элемент реализуется следующей последовательностью действий: сначала производится просмотр массива с целью обнаружения наибольшего элемента, затем осуществляется замена наибольшего элемента на последний элемент с последующим уменьшением размера очереди на единицу. На рис. 9.1 показано содержимое массива для тестовой последовательности операций. Базовая реализация соответствует тем реализациям, которые можно было бы видеть в главе 4 для стеков и очередей небольших размеров (см. профаммы 4.7 и 4.15) и полезны при работе с очередями небольших размеров. Основные различия между ними связаны с их производительностью. Для стеков и очередей есть возможность разрабатывать реализации всех операций, которые выполняются за постоянное время; что касается очередей по приоритетам, то легко отыскать такие реализации, в рамках которых одна из функций вставить или удалить наибольший выполняется за постоянное время, однако найти реализацию, в которой про-

РИСУНОК 9.1. ПРИМЕР ОЧЕРЕДИ ПО ПРИОРИТЕТАМ (ПРЕДСТАВЛЕНИЕ ДАННЫХ В ВИДЕ НЕУПОРЯДОЧЕННОГО МАССИВА)

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

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

Можно использовать упорядоченные и неупорядоченные последовательности, реализованные в виде связных списков или массивов. Выбор в пользу того, оставить элементы неотсортированными или разместить их в определенном порядке, определяется тем, что упорядоченная совокупность элементов позволяет выполнить операции удалить наибольший или найти наибольший за постоянное время, но это также означает необходимость прохода по всему списку, чтобы выполнить операцию вставить. Неупорядоченная последовательность элементов позволяет выполнить операцию вставить за постоянное время, а для операции удалить наибольший или найти наибольший потребуется просмотреть весь список. Неупорядоченность представляет собой прототипный ленивый ПОЦ.ХОЦ. к решению проблемы, в рамках которого выполнение работы откладывается до тех пор, пока это не станет необходимым (в данном случае, поиск наибольшего элемента); упорядоченная последовательность представляет собой прототипный энергичный подход, к решению проблемы, когда заранее выполняется максимально возможный объем работы (поддержка списка отсортированным на случай выполнения операции вставка), дабы обеспечить максимальную эффективность последующих операций, В любом из этих случаев можно использовать представление данных в виде массива или связного списка, при этом основная альтернатива состоит в том, что (двух) связный список позволяет выполнять операцию удалить (и в случае неупорядоченных данных операцию объединить) за постоянное время, но требует большего объема памяти для хранения связей.

Программа 9.2. Реализация очереди по приоритетам с использованием массивов

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

template <class Item> class PQ {

private:

Item *pq; Int N; public:

PQ (int maxN)

{ pq = new Item[maxN]; N = 0; } int entyO const

{return N = 0; } void insert (Item item)

{ pq[N++] = item; } Item getmax( )

{int max = 0;

for (int j = 1; j<N;

if (pq[max] < pq[j]) max = j ; exch(pq[max], pq[N-l]); return pq[-N];