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

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

На рис. 23 и 24 изображены полные бинарные деревья с 16 концевыми узлами (см. раздел 2.3.4.5). Такие деревья удобно хранить в последовательных ячейках памяти, как показано на рис. 25. Заметим, что родителем узла номер к является узел [к/2\, а его потомками являются узлы 2к и2к + 1. Отсюда вытекает еще одно преимущество нисходящего метода - зачастую значительно проще продвигаться вниз от узла к к узлам 2ки2к + 1, чем вверх от узла к к узлам к®1и [к/2\. (Здесь через к®1 обозначено число к + 1 или к -1 в зависимости от того, каким является к: четным или нечетным.)

[16]

Рис. 25. Последовательное распределение памяти для полного бинарного дерева.

До сих пор в примерах выбора из дерева в той или иной мере предполагалось, что N есть степень 2. В действительности можно работать с произвольным значением ЛГ, так как полное бинарное дерево с N концевыми узлами нетрудно построить для любого N.

Мы подошли теперь к основному вопросу: нельзя ли в нисходящем методе обойтись совсем без -оо? Не правда ли, было бы чудесно, если бы всю существенную информацию, которая представлена на рис. 24, удалось расположить в ячейках от 1 до 16 полного бинарного дерева безо всяких бесполезных "дыр", содержащих - оо? Поразмыслив, можно прийти к выводу, что эта цель в действительности достижима, причем не только исключается - оо, но и появляется возможность сортировать записи в пределах того же фрагмента памяти без дополнительной области для накопления результата. Это позволяет получить еще один важный алгоритм сортировки - пирамидальную сортировку (heap-sort). Его автор - Дж. У. Дж. Уильяме (J. W. J. Williams) [САСМ 7 (1964), 347-348].

Пирамидальная сортировка. Будем называть массив ключей Ki,K2,...,Kn пирамидой, если

Ky/2i > Kj при 1 < [j/2\ <j<N. (3)

В этом случае Ki > К2, Ki > Кз, К2 > Ki и т. д. Именно это условие выполняется на рис. 24. Из него следует, в частности, что наибольший ключ оказывается "на вершине пирамиды":

Ki=max{Ki,K2,...,KN). (4)

Если как-нибудь преобразовать произвольный исходный массив в пирамиду, то для получения эффективного алгоритма сортировки можно воспользоваться "нисходящей" процедурой выбора, подобной той, которая описана выше. Эффективный подход к построению пирамиды предложил Р. У. Флойд [R. W. Floyd, САСМ 7 (1964), 701]. Предположим, удалось расположить массив таким образом, что

Kij/2i > Kj при / < [j/2\ <j<N, (5)

где / - некоторое число > 1. (В исходном массиве это условие выполняется автоматически для / = [N/2\, поскольку ни один индекс j не удовлетворяет условию [7V/2J < [j/2\ < j < N.) Нетрудно понять, как, изменяя лишь поддерево с корнем в узле I, преобразовать массив, чтобы распространить неравенства (5) и на случай, когда / = [j/2\. Следовательно, можно уменьшать / на единицу, пока, в конце концов, не будет достигнуто условие (3). Эти идеи Уильямса и Флойда приводят к изящному алгоритму, который заслуживает пристального внимания (рис. 26).

Алгоритм Н {Пирамидальная сортировка). Записи Ri,...,Ri\f перекомпоновываются в пределах того же фрагмента памяти; после завершения сортировки их ключи будут упорядочены следующим образом: Ki < < К. Сначала массив перестраивается в пирамиду, а затем вершина пирамиды многократно исключается и записывается на свое окончательное место. Предполагается, что N >2.

HI. [Начальная установка.] Установить / +- [N/2\ + 1, г i- N.

Н2. [Уменьшить / или г.] Если / > 1, установить I <- I - I, R Ri, К Kt. (Если / > 1, значит, происходит преобразование исходного массива в пирамиду; если же / = 1, значит, ключи Ki К2 . Кг уже образуют пирамиду.) В противном случае установить R <- Rr, К <- Кг, Rr <- Ri и г i- г - I; если в результате оказалось, что г = 1, установить Ri R и завершить выполнение алгоритма.

ИЗ. [Приготовиться к "протаскиванию".] Установить j +- I. (К этому моменту

Kik/2\ > Kk при / < [к/2\ <к<г, (6)

а запись Rk, г < к < N, занимает свое окончательное место. Шаги НЗ-Н8 называются алгоритмом "протаскивания"; выполняемые при этом операции эквивалентны установке Ri i- Rc последующей перекомпоновкой записей Ri,...,Rr таким образом, чтобы условие (6) выполнялось и при I = 1к/2\.)

Н4. [Продвинуться вниз.] Установить i j и j 2j. (На последующих шагах i = LJ/2J.) Если j < г, перейти к шагу Н5; если j = г, перейти к шагу Н6; если же j > г, перейти к шагу ИЗ.

Н5. [Найти большего потомка.] Если Kj < Kj+i, то установить j +- j + 1.

Н6. [Больше, чем АГ?] Если К > Kj, перейти к шагу ИЗ.

Н7. [Поднять его вверх.] Установить Д, <- Rj и возвратиться к шагу Н4.

Н8. [Занести R.] Установить Ri <- R. (На этом алгоритм "протаскивания", начатый на шаге НЗ, заканчивается.) Возвратиться к шагу Н2.

Пирамидальную сортировку иногда описывают как алгоритм. Это обозначение указывает на характер изменения переменных I и г. Верхний треугольник соответствует фазе построения пирамиды, когда г = N, & I убывает до 1; нижний треугольник представляет фазу выбора, когда Z = 1, а г убывает до 1. В табл. 2 показана пирамидальная сортировка все тех же 16 чисел. (В каждой строке изображено состояние в начале шага Н2, скобки указывают на значения переменных /иг.)

Программа Н (Пирамидальная сортировка). Записи, находящиеся в ячейках от INPUT+1 по INPUT+N, сортируются при помощи алгоритма Н. В регистрах записана следующая информация: гП = / - 1, г12 = г - 1, г13 = i, г14 = j, г15 = г - j,

Эта программа приблизительно лишь вдвое длиннее программы S, но при больших N она гораздо более эффективна. Время выполнения программы зависит от следующих параметров: