handle insert(Item); Item getmax(); void change(handle, Item); void remove(handle) ; void join(PQ<Item>&);

В соответствие с обсуждениями в разделе 9.1, реализация, представленная в программах 9.9 и 9.10, подходит для тех приложений, в которых очередь по приоритетам небольшая и операции удалить наибольший или найти наибольший выполняются нечасто; в остальных случаях более предпочтительными оказываются реализации на базе пирамидальной сортировки. Реализация функции fixUp и fixDown на пирамидально упорядоченных деревьях с явными связями с одновременной поддержкой целостности дескрипторов - достаточно сложная задача, которую мы оставляем читателю в качестве упражнения, а сами займемся подробным рассмотрением двух альтернативных подходов в разделах 9.6 и 9.7.

Полный АТД, такой как в программе 9.8, обладает массой достоинств, однако иногда полезно рассматривать другие подходы, налагающие другие ограничения на клиентские программы и реализации. В разделе 9.6 рассматривается пример, в условиях которого в обязанности клиентской программы входит ведение записей и ключей, а программы, работающие с очередями по приоритетам, обращаются к ним неявно.

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

Программа 9.9. Неупорядоченная очередь по приоритетам

в виде двухсвязного списка.

Эта реализация содержит операции создать (construct), проверить на наличие элементов (test if empty) и вставить (insert), взятые из интерфейса программы 9.8 (см. программу 9.10, в которой содержатся реализации четырех других функций). Она поддерживает простой неупорядоченный список, в котором имеются головной и хвостовой узлы. Структура node (узел) описывается как узел двухсвязного списка (элемент и две связи). Представление приватных данных состоит из головы списка и хвостовых связей.

Template <class Item> class PQ {

private:

struct node

{ Item item; node *prev, *next; node (Item v)

{ item = v; prev = 0; next = 0; }

typedef node* link; link head, tail; public:

typedef node* handle; PQ(int = 0) {

head = new node(O); tail - new node(O); head->prev = tail; head->next = tail; tail->prev = head; tail->next = head;

int fuapty( > const

{ return head->next->next == head; } handle insert(Item v)

{ handle t = new node (v) ;

t->next = head->next; t->next->prev = t; t->prev = head; head->next = t; return t;

Item getmax( ); void change(handle, Item); void remove(handle); void join (PQ<It€Mn>&) ;

Добавление таких процедур в интерфейс, представленный в программе 9.8, не связан с какими-либо трудностями; гораздо труднее разработать такую реализацию, в рамках которой гарантируется логарифмическая производительность для всех видов операций. В тех приложениях, в которых очереди по приоритетам не достигают больших размеров или в которых смесь операций вставить и удалить наибольший обладает рядом специальных свойств, предпочтительным может оказаться полностью гибкий интерфейс. С другой стороны, в тех приложениях, в которых очереди возрастают до внушительных размеров и наблюдается или подтверждается соответствуюшими расчетами десятикратное, а то и стократное возрастание производительности, можно ограничиться именно теми операциями, которые обеспечивают упомянутый рост производительности. Были проведены обширные исследования, результаты которых были положены в основу алгоритмов, манипулирующих очередями по приоритетам при помощи различных сочетаний операций. Биномиальная очередь, описанная в разделе 9.7, представляет собой важный пример такого рода.

Программа 9.10. Очередь по приоритетам в виде двухсвязного списка (продолжение)

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

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

список узлов из параметров, которые дoJ[lжны быть включены в результат, но при этом она не делает их копий.

Item getmax( )

{ Item max; link x = head->next;

for (link t = x; t->next !=head; t = t->next) if (x->item < t->item) x =t; max - x->item; remove (x) ; return max; }

void change (handle x. Item v)

{ x->key = v; } void remove(handle x)

x->next->prev-> = x->prev; x->prev->next-> = x->next; delete x;

void join(PQ<Item>S p)

tail-> prev ->next = p.head->next; p.head->next->prev = tail-> prev; head->prev = p.tail; p.tail->next = head; delete tail; delete p.head; tail = p. tail

Упражнения

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

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

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

9.41. Построить реализации операций вставить, удалить наибольший, изменить приоритет и удалить (интерфейс очереди по приоритетам в программе 9.8), воспользовавшись пирамидально упорядоченными деревьями с явными связями. Совет: Поскольку в клиентской программе имеются дескрипторы конкретных элементов структуры данных, это упражнение сложнее упражнения 9.40 не только потому, что узлы должны быть трехсвязными, но также и потому, что ваши программы могут изменять только связи (но не ключи) в узлах.

10 программой FinePnn