HI. Начальная установка

Н2. Уменьшить / или г

ИЗ. Приготовиться к "протаскиванию"

г=г = 1

Н4. Продвинуться вниз

Н5. Найти большего потомка

Н8. Занести R

Нет/Нб. Больше, чем А-?

Н7. Поднять его вверх

j = r

Рис. 26. Пирамидальная сортировка; пунктиром обозначен алгоритм "протаскивания".

Таблица 2

ПРИМЕР ПИРАМИДАЛЬНОЙ СОРТИРОВКИ

Р = N + [N/2\ - 2 - число проходов с "протаскиванием";

А - число "протаскиваний", при которых ключ К, в конце концов, попадает

во внутренний узел пирамиды; В - суммарное число ключей, просмотренных во время "протаскиваний"; С - число присваиваний j + 1 на шаге Н5; D - число случаев, когда j = г на шаге Н4.

Эти параметры проанализированы ниже; как показывают эксперименты, они лишь незначительно отклоняются от средних значений:

А й 0.349iV, В W iV Ig iV - 1.87iV,

Сг» iiVlgiV-0.94iV, DwlniV.

При N = 1000, например, четыре эксперимента со случайными исходными данными показали соответственно результаты А = 371, 351, 341, 340, В = 8055, 8072, 8094, 8108, С = 4056, 4087, 4017, 4083 и £» = 12, 14, 8, 13. Общее время выполнения программы 7А + ЫВ + 4С + 20iV - 2D + 15[iV/2j - 28 равно, таким образом, в среднем примерно 16iVlgiV + O.OliV машинных циклов. Глядя на табл. 2, трудно поверить в то, что пирамидальная сортировка так уж эффективна: большие ключи перемещаются влево, прежде чем мы успеваем отложить их вправо! Это и в самом деле странный способ сортировки при малых N. Время сортировки 16 ключей из табл. 2 равно 1068м, тогда как при обычным методе простых вставок (программа 5.2.IS) требуется всего 514м. Сортировка посредством простого выбора (программа S) отнимает 853м.

При больших N программа Н более эффективна. Напрашивается сравнение с сортировкой методом Шелла с убывающим смещением (программа 5.2.Ш) и быстрой сортировкой Хоара (программа 5.2.2Q), так как во всех трех программах сортировка выполняется путем сравнения ключей, причем требуется довольно малый объем дополнительной памяти или она не используется вовсе. При N - 1000 значения среднего времени выполнения равны приблизительно

160000м для пирамидальной сортировки, 130000м для сортировки методом Шелла, 80000м для быстрой сортировки.

(MIX - типичный представитель большинства компьютеров, но, разумеется, на конкретных машинах получатся несколько иные относительные величины.) С ростом N пирамидальная сортировка превзойдет по скорости метод Шелла, но асимптотическое выражение для времени выполнения 16NlgN й 23.08iVIniV никогда не станет лучше выражения для быстрой сортировки 11.67iVIniV. Модификация пирамидальной сортировки, которая будет проанализирована в упр. 18, ускорит процесс вследствие снижения числа сравнений, но даже с этим усовершенствованием пирамидальная сортировка проигрывает по сравнению с быстрой сортировкой.

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

<1.5iV, B<N[\gN\, C<N[lgN}. (8)

Таким образом, независимо от распределения исходных данных выполнение программы Н не займет более 18iV[lgiVJ + 38N машинных циклов. Пирамидальная сортировка - первый из рассмотренных нами до сих пор методов сортировки, время работы которого заведомо имеет порядок N log N. Сортировка посредством слияний, которая будет обсуждаться ниже, в разделе 5.2.4, тоже обладает таким свойством, но этот метод требует больше памяти.

Наибольший из включенных первым исключается. В главе 2 было показано, что линейные списки часто целесообразно классифицировать по характеру выполнения операций включения и исключения. Стек ведет себя по принципу "последним пришел - первым вышел" в том смысле, что при каждом исключении удаляется самый младший элемент списка (элемент, который был вставлен позже всех других элементов, присутствующих в данный момент в списке). Простая очередь ведет себя по принципу "первым пришел - первым вышел" в том смысле, что при каждом исключении удаляется самый старший из имеющихся элементов. В более сложных ситуациях, в таких как пример с моделированием лифта из раздела 2.2.5, необходим список наподобие "наименьший из включенных первым исключается" в котором при каждом исключении удаляется элемент, имеющий наименьший ключ. Такой список можно назвать приоритетной очередью, поскольку ключ каждого элемента отражает его относительную способность быстро покидать список. Сортировка посредством выбора - частный случай приоритетной очереди, над которой производится сначала N операций вставки, а затем N операций удаления.

Приоритетные очереди возникают в самых разнообразных приложениях. Например, в некоторых численных итеративных схемах повторяется выбор элемента, имеющего наибольшее (или наименьшее) значение некоторого проверяемого критерия. Параметры выбранного элемента изменяются, и он снова вставляется в список с новым значением критерия, соответствующим новым значениям параметров. Приоритетные очереди часто используются в операционных системах при планировании заданий. Другие типичные применения приоритетных очередей упоминаются в упр. 15, 29 и 36; кроме того, много примеров будет приведено в следующих главах.

Как же реализовать приоритетную очередь? Один из очевидных способов сделать это - организовать и поддерживать порядок по ключам в рассортированном списке элементов. Тогда включение нового элемента, по существу, будет сведено к задаче, рассмотренной при изучении сортировки методом вставок в разделе 5.2.1. При другом, еще более очевидном, способе работы с приоритетной очередью элементы в списке хранятся в произвольном порядке. Тогда для выбора нужного элемента приходится осуществлять поиск наибольшего (или наименьшего) ключа каждый раз, когда необходимо сделать исключение. В обоих этих очевидных подходах неприятность состоит в том, что необходимо порядка Q{N) шагов для выполнения либо операции вставки, либо операции удаления, если в списке содержится N элементов, т. е. при больших N эти операции отнимают слишком много времени.

В своей статье о пирамидальной сортировке Уильяме (Williams) обратил внимание на то, что пирамиды идеально подходят для приложений с большими приоритетными очередями, так как элемент можно вставить в пирамиду или удалить из нее за О (log N) шагов. К тому же все элементы пирамиды компактно располагаются