operator< для аргументов типа Index, как указано в комментарии, предшествующем программе 9.11, то когда fixUp выполняет сравнение pq[j] с pq[k], она, по идее, сравнивает data.grade[pq[j]] с data.grade[pq[j]]. Мы предполагаем, что Index - это класс-оболочка, объект которого может индексировать массивы, так что мы можем зафиксировать позицию сортирующего дерева, соответствующую значению индекса к в qpik], что, в свою очередь, позволяет реализовать операции изменить приоритет и удалить (см. рис. 9.13). Инвариант pq[qp[k]] = qp[pq[k]] = к поддерживается для всех к сортирующего дерева (см. рис. 9.13).

template <class Item> class PQ {

private:

int N; Index* pq; int* qp; void exch(Index i. Index j) { int t;

t = qpti]; qpti] = qptjl ; qptl] = t; pqtqpti]] = i; pqtqptj]] = j;

void fixUp(Index a[] , int Ic) ;

void fixDown (Index а[] , int k, int N) ;

public:

PQ(int maxN)

{ pq s new Index [maxN+l] ;

qp = new int[maxN- -l] ; N = 0; } int empty ( ) const

{ return N = 0; } void insert(Index, v)

{ pqt++N] v; qptv] = N; fixUp(qp, N) ; } Index getmax ( ) {

exch(pq[13, pqtN]); fixDown (qp, 1, N-l); return qptN-] ;

void change(Index k)

{ fixUp(pq, qptk]); fixDown (pq, qptk], N); }

Сопоставление этого подхода, обеспечивающего реализацию очереди по приоритетам в полном объеме, с подходом из раздела 9.5, обнаруживает существенные различие в конструкции АТД. В первом случае (программа 9.8, например) в обязанность реализации очереди по приоритетам входит распределение памяти под ключи и ее освобождение, изменение значений ключей и тому подобное. Абстрактный тип данных предоставляет клиентской программе дескрипторы элементов данных, а эта программа осуществляет доступ к элементам данных только за счет обращений к программам поддержки очередей по приоритетам, передавая эти дескрипторы в параметрах. Во втором случае (например, программа 9.12) клиентская программа несет ответственность за ключи и записи, а программы поддержки очереди по приоритетам осуществляют доступ к этой информации только через дескрипторы, выбранные пользователем (индексы массива в случае программы 9.12). В обоих случаях требуется обеспечить взаимодействие между клиентской программой и реализацией.

9.7. Биномиальные очереди

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

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

Упражнения

9.48. Предположим, что массив заполнен ключами EASYQUESTION. Показать содержимое массивов pq и qp после помещения этих ключей в первоначально пустое сортирующее дерево, используя программу 9.12.

о 9.49. Добавить в программу 9.12 операцию удалить.

9.50. Реализовать АТД очереди по приоритетам для индексных элементов (см программу 9.11), воспользовавшись представлением очереди по приоритетам в виде упорядоченного массива.

9.51. Реализовать АТД очереди по приоритетам для индексных элементов (см. программу 9.11), воспользовавшись представлением очереди по приоритетам в виде неупорядоченного массива.

о 9.52. Для заданного массива из элементов рассмотрим полное бинарное дерево из 2N элементов (представленном в виде массива pq), содержащих индексы из этого массива, со следующими свойствами: (/) для i от О до N-1 имеем pq[N+i] и (/7) для i от 1 до Л- 1 имеем pq[i] = pq[2*i], если a[pq[2*i]]>a[pq[2*i+l]], и pq[i]= pq[2*i+l] - в противном случае. Такая структура называется турниром индексного сортирующего дерева (index heap tournament), поскольку сочетает свойства индексных сортирующих деревьев и турниров (см. программу 5.19). Запишите турнир индексного сортирующего дерева, соответствующий ключам EASYQUEST ION.

о 9.53. Реализовать АТД очереди по приоритетам для индексных элементов (см. программу 9.11), используя турнир индексного сортирующего дерева.

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

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

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

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