в последовательных ячейках памяти. Фаза выбора в алгоритме Н - это последовательность шагов удаления в процессе наподобие наибольший из включенных первым исключается: чтобы исключить наибольший элемент Ki, удаляем его и "протаскиваем" элемент в новой пирамиде из iV - 1 элементов. (Если нужен алгоритм "наименьший из включенных первым исключается" как в примере с лифтом, то, очевидно, можно изменить определение пирамиды, заменив в (3) знак ">" знаком "<". Для удобства будем рассматривать здесь лишь случай "наибольший из включенных первым исключается".) Вообще, если требуется исключить наибольший элемент, а затем вставить новый элемент х, можно выполнить процедуру "протаскивания" при 1 = 1, г = МиК = х. Если же необходимо вставить элемент без предварительного исключения, можно воспользоваться "восходящей" процедурой из упр. 16.

Связанное представление приоритетных очередей. Эффективный способ представления приоритетных очередей в виде связанных бинарных деревьев предложил в 1971 году Кларк Э. Крэйн [см. Clark А. Сгапе, Technical Report STAN-CS-72-259 (Computer Science Department, Stanford University, 1972)]). Его метод требует наличия в каждой записи двух полей связи и короткого поля счетчика, но по сравнению с пирамидами он обладает следующими преимуществами.

i) Если с приоритетной очередью работают, как со стеком, то операции включения и исключения более эффективны (они отнимают фиксированное время, не зависящее от длины очереди).

ii) Записи никогда не перемещаются, изменяются только указатели.

iii) Можно слить две непересекающиеся приоритетные очереди, содержащие в общей сложности N элементов, всего за O(logiV) шагов.

Немного видоизмененный метод Крэйна проиллюстрирован на рис. 27, на котором показан особый тип структуры бинарного дерева. В каждом узле содержатся поле KEY, поле DIST и два поля связи - LEFT и RIGHT. Поле DIST всегда устанавливается равным длине кратчайшего пути от этого узла до конечного узла (т. е. до пустого узла Л дерева). Если считать, что DIST(A) = О и KEY(A) = -оо, то поля KEY и DIST в этом дереве удовлетворяют следующим соотношениям:

KEY(P) > KEY(LEFT(P)), KEY(P) > KEY(RIGHT(P)); (9)

DIST(P) = 1 --min(DIST(LEFT(P)),DIST(RIGHT(P))); (10)

DIST(LEFT(P)) > DIST(RIGHT(P)). (11)

Соотношение (9) аналогично условию существования пирамиды (3) и служит гарантией того, что в корне дерева находится наибольший ключ, а соотношение (10) - это просто определение поля DIST, сформулированное выше. Соотношение (И) представляет собой интересное новшество: из него следует, что кратчайший путь к конечному узлу всегда можно получить, двигаясь вправо. Будем называть бинарное дерево с этим свойством левосторонним деревом, поскольку оно, как правило, сильно "тянется" влево.

Из этих определений ясно, что равенство DIST(P) = п подразумевает существование, по крайней мере, 2" пустых поддеревьев, расположенных ниже Р; в противном случае нашелся бы более короткий путь от Р до концевого узла Л. Таким образом, если в левостороннем дереве имеется N узлов, то путь, ведущий из корня вниз по направлению вправо, содержит не более чем [Ig(iV -- 1)J узлов. Новый

275 1

4261 1

677 1

7031 1

612 1

509 1

170 1

£3

1541 1

±4:

512 2

503 I 1

061 1

087 1

Формат ysia

Рис. 27. Приоритетная очередь, представленная в виде левостороннего дерева.

узел можно вставить в приоритетную очередь, пройдя по этому пути (см. упр. 33). Следовательно, в худшем случае необходимо всего O(logiV) шагов. Наилучший случай достигается, когда дерево линейно (все связи RIGHT равны Л), а наихудший случай - когда оно абсолютно сбалансировано.

Чтобы удалить узел из корня, нужно просто слить два его поддерева. Операция слияния двух непересекающихся левосторонних деревьев, на которые ссылаются указатели Р и Q, по своей идее проста: если KEY(P) > KEY(Q), то берем в качестве корня Р и сливаем Q с правым поддеревом Р. При этом изменится DIST(P), а LEFT(P) поменяется местами с RIGHT(Р) в случае необходимости. Нетрудно составить подробное описание этого процесса (см. упр. 33).

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

Мы видели, что операции над левосторонними деревьями, в целом, выполняются несколько быстрее, чем операции над пирамидами, но пирамиды занимают

меньше памяти. Сбалансированные деревья занимают примерно столько же памяти, сколько левосторонние (быть может, чуть меньше); операции над ними выполняются .медленнее, чем над пирамидами, и программирование сложнее, но структура сбалансированных деревьев в некоторых отношениях существенно более гибкая. Рс1ботая с пирамидами, не так просто предсказать, что произойдет с элементами, если у них равные ключи. Нельзя гарантировать, что элементы с равными ключами будут обрабатываться по принципу "последним пришел - первым вышел" или "первым пришел - первым вышел", если только ключ не расширен и не содержит дополнительного поля "порядковый номер вставки"; тогда равных ключей просто нет. С другой стороны, если применять сбалансированные деревья, можно легко оговорить жесткие условия, относящиеся к равным ключам. Можно также выполнять такие действия, как "вставить х непосредственно перед (или после) у". Сбалансированные деревья симметричны, так что в любой момент можно исключить либо наибольший, либо наименьший элемент, в то время как левосторонние деревья и пирамиды должны быть так или иначе ориентированы. (См., тем не менее, упр. 31, в котором показано, как строить симметричные пирамиды.) Сбалансированные деревья можно использовать и для поиска, и для сортировки. Из сбалансированного дерева можно довольно быстро удалять последовательные блоки элементов. Но два сбалансированных дерева нельзя слить менее чем за N) шагов, в то время как два левосторонних дерева можно слить всего за О (log N) шагов.

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

Со времени выхода, в свет "пионерской" работы Унльямса и Крэйна разработано много новых способов представления приоритетных очередей. Теперь в распоряжении программистов имеется большое разнообразие опций, помимо простых списков, левосторонних и сбалансированных деревьев. Некоторые из них перечислены ниже:

• спрямленные деревья, которые обеспечивают обработку симметричной приоритетной очереди всего за О (log log М) шагов, если все ключи лежат в заданном диапазоне О < К < М [Р. van Emde Boas, R. Kaas, E. Zijlstra, Math. Systems Theory 10 (1977), 99-127];

• биномиальные очереди [J. Vuillemin, CACM 12 (1978), 309-315; M. R. Brown, SICOMP 7 (1978), 298-319];

• пагоды [J. Frangon, G. Viennot, J. Vuillemin, FOCS 19 (1978), 1-7];

• парные пирамиды [М. L. Fredman, R. Sedgewick, D. D. Sleator, R. E. Tarjan, igorithmica 1 (1986), 111-129; J. T. Stasko, J. S. Vitter, CACM 30 (1987), 234-249];

• спиральные пирамиды [D. D. Sleator, R. E. Tarjan, SICOMP 15 (1986), 52-59];

• пирамиды Фибоначчи [М. L. Fredman, R. E. Tarjan, JACM 34 (1987), 596-615] и более общие AF-пирамиды [М. L. Fredman, D. E. Willard, J. Computer and System Sci. 48 (1994), 533-551];

• календарные очереди [R. Brown, CACM 31 (1988), 1220-1227; G. A. Davison, CACM 32 (1989), 1241-1243];