\input style
%%172 
\proof хСЛИ ПРОИЗВЕДЕНО МЕНЕЕ $n-1$ СРАВНЕНИЙ, ТО НАЙДУТСЯ ПО КРАЙНЕЙ МЕРЕ 
ДВА ЭЛЕМЕНТА, ДЛЯ КОТОРЫХ НЕ БЫЛО ОБНАРУЖЕНО НИ ОДНОГО ЭЛЕМЕНТА, 
ПРЕВОСХОДЯЩЕГО ИХ ПО ВЕЛИЧИНЕ. ёЛЕДОВАТЕЛЬНО, МЫ ТАК И НЕ УЗНАЕМ, 
КОТОРЫЙ ИЗ ЭТИХ ДВУХ ЭЛЕМЕНТОВ БОЛЬШЕ, И, ЗНАЧИТ, НЕ СМОЖЕМ ОПРЕДЕЛИТЬ МАКСИМУМ.
\proofend

ЄАКИМ ОБРАЗОМ, ПРОЦЕСС ВЫБОРА, В КОТОРОМ ОТЫСКИВАЕТСЯ НАИБОЛЬШИЙ ЭЛЕМЕНТ, 
ДОЛЖЕН СОСТОЯТЬ НЕ МЕНЕЕ ЧЕМ ИЗ $n-1$ ШАГОВ. юЗНАЧАЕТ ЛИ ЭТО, ЧТО ДЛЯ ВСЕХ 
МЕТОДОВ СОРТИРОВКИ, ОСНОВАННЫХ НА $n$ ПОВТОРНЫХ ВЫБОРАХ, ЧИСЛО ШАГОВ 
НЕИЗБЕЖНО БУДЕТ ПОРЯДКА $n^2$? ъ СЧАСТЬЮ, ЛЕММА M ПРИМЕНИМА ТОЛЬКО К 
\emph{ПЕРВОМУ} ШАГУ ВЫБОРА; ПРИ ПОСЛЕДУЮЩИХ ВЫБОРАХ МОЖНО 
ИСПОЛЬЗОВАТЬ ИЗВЛЕЧЕННУЮ РАНЕЕ ИНФОРМАЦИЮ. эАПРИМЕР, В УПР.~8 ПОКАЗАНО,
 ЧТО СРАВНИТЕЛЬНО ПРОСТОЕ ИЗМЕНЕНИЕ АЛГОРИТМА~S НАПОЛОВИНУ СОКРАЩАЕТ ЧИСЛО СРАВНЕНИЙ.

ЁАССМОТРИМ 16 ЧИСЕЛ, ПРЕДСТАВЛЕННЫХ В 1-Й СТРОКЕ В ТАБЛ.~1. юДИН ИЗ 
СПОСОБОВ СЭКОНОМИТЬ ВРЕМЯ ПРИ ПОСЛЕДУЮЩИХ 
ВЫБОРАХ---РАЗБИТЬ ВСЕ ЧИСЛА НА ЧЕТЫРЕ ГРУППЫ ПО ЧЕТЫРЕ ЧИСЛА. эАЧАТЬ МОЖНО С 
ОПРЕДЕЛЕНИЯ НАИБОЛЬШЕГО, ЭЛЕМЕНТА КАЖДОЙ ГРУППЫ, А ИМЕННО СООТВЕТСТВЕННО С КЛЮЧЕЙ
$$
512, 908, 653, 765;
$$
ТОГДА НАИБОЛЬШИЙ ИЗ ЭТИХ ЧЕТЫРЕХ ЭЛЕМЕНТОВ 908 И БУДЕТ НАИБОЛЬШИМ ВО 
ВСЕМ ФАЙЛЕ. ўТОБЫ ПОЛУЧИТЬ ВТОРОЙ ПО ВЕЛИЧИНЕ ЭЛЕМЕНТ, ДОСТАТОЧНО 
ПРОСМОТРЕТЬ СНАЧАЛА ОСТАЛЬНЫЕ ТРИ ЭЛЕМЕНТА ГРУППЫ, СОДЕРЖАЩЕЙ 908; 
НАИБОЛЬШИЙ ИЗ $\{170, 897, 275\}$ РАВЕН 897, И ТОГДА НАИБОЛЬШИЙ СРЕДИ
$$
512, 897, 653, 765
$$
ЭТО 897. рНАЛОГИЧНО, ДЛЯ ТОГО ЧТОБЫ ПОЛУЧИТЬ ТРЕТИЙ ПО ВЕЛИЧИНЕ ЭЛЕМЕНТ, 
ОПРЕДЕЛЯЕМ НАИБОЛЬШИЙ ИЗ $\{170, 275\}$, А ЗАТЕМ НАИБОЛЬШИЙ ИЗ
$$
512, 275, 653, 765
$$
И Т. Д. ъАЖДЫЙ ВЫБОР, КРОМЕ ПЕРВОГО, ТРЕБУЕТ НЕ БОЛЕЕ 6 ДОПОЛНИТЕЛЬНЫХ 
СРАВНЕНИЙ. тООБЩЕ, ЕСЛИ $N$---ТОЧНЫЙ КВАДРАТ, ТО МОЖНО РАЗДЕЛИТЬ ФАЙЛ НА 
$\sqrt N$ ГРУПП ПО $\sqrt N$ ЭЛЕМЕНТОВ В КАЖДОЙ;
ЛЮБОЙ ВЫБОР, КРОМЕ ПЕРВОГО, ТРЕБУЕТ НЕ БОЛЕЕ ЧЕМ $\sqrt{N}-1$ СРАВНЕНИЙ 
ВНУТРИ ГРУППЫ РАНЕЕ ВЫБРАННОГО ЭЛЕМЕНТА ПЛЮС $\sqrt{N}-1$ СРАВНЕНИЙ СРЕДИ 
"ЛИДЕРОВ ГРУПП". ¤ТОТ МЕТОД ПОЛУЧИЛ НАЗВАНИЕ "КВАДРАТИЧНЫЙ ВЫБОР"; ОБЩЕЕ 
ВРЕМЯ РАБОТЫ ДЛЯ НЕГО ЕСТЬ $O(N\sqrt{N})$, ЧТО СУЩЕСТВЕННО ЛУЧШЕ, ЧЕМ $O(N^2)$.

ьЕТОД КВАДРАТИЧНОГО ВЫБОРА ВПЕРВЫЕ ОПУБЛИКОВАН 
¤.~X.~ЇРЭНДОМ [{\sl JACM\/}, {\bf 3} (1956), 152--154]; ОН УКАЗАЛ, ЧТО ЭТУ 
ИДЕЮ МОЖНО .ОБОБЩИТЬ, ПОЛУЧИВ В РЕЗУЛЬТАТЕ МЕТОД КУБИЧЕСКОГО ВЫБОРА, 
ВЫБОРА ЧЕТВЕРТОЙ СТЕПЕНИ И Т. Д. эАПРИМЕР, МЕТОД КУБИЧЕСКОГО
%%173
ВЫБОРА СОСТОИТ В ТОМ, ЧТОБЫ РАЗДЕЛИТЬ ФАЙЛ НА $\root 3\of N$ БОЛЬШИХ ГРУПП,
 КАЖДАЯ ИЗ КОТОРЫХ СОДЕРЖИТ ПО $\root 3\of N$ МАЛЫХ ГРУПП ПО $\root 3\of 
N$ ЗАПИСЕЙ; ВРЕМЯ РАБОТЫ ПРОПОРЦИОНАЛЬНО $N\root 3\of N$. хСЛИ РАЗВИТЬ 
ЭТУ ИДЕЮ ДО ЕЕ ПОЛНОГО ЗАВЕРШЕНИЯ, ТО МЫ ПРИДЕМ К ТОМУ, ЧТО ЇРЭНД НАЗВАЛ 
"ВЫБОР $n$-Й СТЕПЕНИ", ОСНОВАННЫЙ НА СТРУКТУРЕ БИНАРНОГО ДЕРЕВА. тРЕМЯ 
РАБОТЫ ЭТОГО МЕТОДА ПРОПОРЦИОНАЛЬНО $N \log N$; МЫ БУДЕМ НАЗЫВАТЬ ЕГО 
\dfn{ВЫБОРОМ ИЗ ДЕРЕВА}.
\section тЫБОР ИЗ ДЕРЕВА. яРИНЦИПЫ СОРТИРОВКИ ПОСРЕДСТВОМ ВЫБОРА ИЗ ДЕРЕВА 
БУДЕТ ЛЕГЧЕ ВОСПРИНЯТЬ, ЕСЛИ ВОСПОЛЬЗОВАТЬСЯ АНАЛОГИЕЙ С ТИПИЧНЫМ 
"ТУРНИРОМ С ВЫБЫВАНИЕМ". ЁАССМОТРИМ, НАПРИМЕР, РЕЗУЛЬТАТЫ СОРЕВНОВАНИЯ 
ПО НАСТОЛЬНОМУ ТЕННИСУ, ПОКАЗАННЫЕ НА РИС.~22. фЖИМ ПОБЕЖДАЕТ фОНА, А 
фЖО ПОБЕЖДАЕТ фЖЕКА; ЗАТЕМ В СЛЕДУЮЩЕМ ТУРЕ фЖО ВЫИГРЫВАЕТ У фЖИМА И Т. Д.

эА РИС.~22 ПОКАЗАНО, ЧТО фЖО---ЧЕМПИОН СРЕДИ ВОСЬМИ СПОРТСМЕНОВ, А ДЛЯ 
ТОГО, ЧТОБЫ ОПРЕДЕЛИТЬ ЭТО, ПОТРЕБОВАЛОСЬ $8-1=7$ МАТЧЕЙ (Т. Е. СРАВНЕНИЙ).
 фИК ВОВСЕ НЕ ОБЯЗАТЕЛЬНО БУДЕТ ВТОРЫМ ПО СИЛЕ ИГРОКОМ: ЛЮБОЙ ИЗ 
СПОРТСМЕНОВ, У КОТОРЫХ ВЫИГРАЛ фЖО, ВКЛЮЧАЯ ДАЖЕ ПРОИГРАВШЕГО В ПЕРВОМ 
ТУРЕ фЖЕКА, МОГ БЫ ОКАЗАТЬСЯ ВТОРЫМ ПО СИЛЕ ИГРОКОМ. тТОРОГО ИГРОКА МОЖНО 
ОПРЕДЕЛИТЬ, ЗАСТАВИВ фЖЕКА СЫГРАТЬ С фЖИМОМ, А ПОБЕДИТЕЛЯ ЭТОГО МАТЧА---С 
фИКОМ; ВСЕГО ДВА ДОПОЛНИТЕЛЬНЫХ МАТЧА ТРЕБУЕТСЯ ДЛЯ ОПРЕДЕЛЕНИЯ ВТОРОГО ПО 
СИЛЕ ИГРОКА, ИСХОДЯ ИЗ ТОГО СООТНОШЕНИЯ СИЛ, КОТОРОЕ МЫ ЗАПОМНИЛИ ИЗ 
ПРЕДЫДУЩИХ ИГР.

тООБЩЕ МОЖНО "ВЫВЕСТИ" ИГРОКА, НАХОДЯЩЕГОСЯ В КОРНЕ ДЕРЕВА, И ЗАМЕНИТЬ ЕГО 
ЧРЕЗВЫЧАЙНО СЛАБЫМ ИГРОКОМ. яОДСТАНОВКА ЭТОГО СЛАБОГО ИГРОКА ОЗНАЧАЕТ, 
ЧТО ПЕРВОНАЧАЛЬНО ВТОРОЙ ПО СИЛЕ СПОРТСМЕН СТАНЕТ ТЕПЕРЬ НАИЛУЧШИМ, И 
ИМЕННО ОН ОКАЖЕТСЯ В КОРНЕ, ЕСЛИ ВНОВЬ ВЫЧИСЛИТЬ ПОБЕДИТЕЛЕЙ В 
ВЕРХНИХ УРОВНЯХ ДЕРЕВА. фЛЯ ЭТОГО НУЖНО ИЗМЕНИТЬ ЛИШЬ ОДИН ПУТЬ, В ДЕРЕВЕ, 
ТАК ЧТО ДЛЯ ВЫБОРА СЛЕДУЮЩЕГО ПО СИЛЕ ИГРОКА НЕОБХОДИМО МЕНЕЕ $\lceil 
\log_2 N\rceil$) ДОПОЛНИТЕЛЬНЫХ СРАВНЕНИЙ. ёУММАРНОЕ
%%174
\picture{ЁИС. 23. яРИМЕР СОРТИРОВКИ ПОСРЕДСТВОМ ВЫБОРА ИЗ ДЕРЕВА...}
%% 175
ВРЕМЯ ВЫПОЛНЕНИЯ ТАКОЙ СОРТИРОВКИ ПОСРЕДСТВОМ ВЫБОРА ПРИМЕРНО 
ПРОПОРЦИОНАЛЬНО $N\log N$.

эА РИС.~23 СОРТИРОВКЕ ПОСРЕДСТВОМ ВЫБОРА ИЗ ДЕРЕВА ПОДВЕРГАЮТСЯ НАШИ 16 
ЧИСЕЛ. чАМЕТИМ, ЧТО ДЛЯ ТОГО, ЧТОБЫ ЗНАТЬ, КУДА ВСТАВЛЯТЬ СЛЕДУЮЩИЙ 
ЭЛЕМЕНТ "$-\infty$", НЕОБХОДИМО ПОМНИТЬ, ОТКУДА ПРИШЕЛ КЛЮЧ, НАХОДЯЩИЙСЯ В 
КОРНЕ. яОЭТОМУ УЗЛЫ РАЗВЕТВЛЕНИЯ В ДЕЙСТВИТЕЛЬНОСТИ СОДЕРЖАТ УКАЗАТЕЛИ 
ИЛИ ИНДЕКСЫ, ОПИСЫВАЮЩИЕ ПОЗИЦИЮ КЛЮЧА, А НЕ САМ КЛЮЧ. юТСЮДА СЛЕДУЕТ, ЧТО 
НЕОБХОДИМА ПАМЯТЬ ДЛЯ $N$ ИСХОДНЫХ ЗАПИСЕЙ, $N-1$ СЛОВ-УКАЗАТЕЛЕЙ И $N$ 
ВЫВОДИМЫХ ЗАПИСЕЙ. (ЁАЗУМЕЕТСЯ, ЕСЛИ ВЫВОД
\picture{ЁИС. 24.  яРИМЕНЕНИЕ КОРПОРАТИВНОЙ СИСТЕМЫ ВЫДВИЖЕНИЙ К 
СОРТИРОВКЕ. ъАЖДЫЙ ПОДНИМАЕТСЯ НА СВОЙ УРОВЕНЬ НЕКОМПЕТЕНТНОСТИ В ИЕРАРХИИ.}
ИДЕТ НА ЛЕНТУ ИЛИ НА ДИСК, ТО НЕ НУЖНО СОХРАНЯТЬ ВЫВОДИМЫЕ ЗАПИСИ В 
ОПЕРАТИВНОЙ ПАМЯТИ.)

ўТОБЫ ОЦЕНИТЬ ТЕ ЗАМЕЧАТЕЛЬНЫЕ УСОВЕРШЕНСТВОВАНИЯ, КОТОРЫЕ МЫ СОБИРАЕМСЯ 
ОБСУДИТЬ, В ЭТОМ МЕСТЕ СЛЕДУЕТ ПРЕРВАТЬ ЧТЕНИЕ ДО ТЕХ ПОР, ПОКА ВЫ НЕ 
ОСВОИТЕСЬ С ВЫБОРОМ ИЗ ДЕРЕВА ХОТЯ БЫ НАСТОЛЬКО, ЧТО РЕШЕНИЕ УПР.~10 НЕ 
СОСТАВИТ ДЛЯ ВАС НИКАКОГО ТРУДА.

юДНА ИЗ МОДИФИКАЦИЙ ВЫБОРА ИЗ ДЕРЕВА, ВВЕДЕННАЯ, ПО СУЩЕСТВУ, 
ъ.~¤.~рЙВЕРСОНОМ [A Programming Language (Wiley, 1962), 223--227], 
УСТРАНЯЕТ НЕОБХОДИМОСТЬ УКАЗАТЕЛЕЙ, СЛЕДУЮЩИМ ОБРАЗОМ ОСУЩЕСТВЛЯЯ 
"ЗАГЛЯДЫВАНИЕ ВПЕРЕД": КОГДА ПОБЕДИТЕЛЬ МАТЧА НА НИЖНЕМ УРОВНЕ ПОДНИМАЕТСЯ 
ВВЕРХ, ТО НА НИЖНЕМ УРОВНЕ ЕГО СРАЗУ ЖЕ МОЖНО ЗАМЕНИТЬ НА "$-\infty$"; 
КОГДА ЖЕ ПОБЕДИТЕЛЬ ПЕРЕМЕЩАЕТСЯ ВВЕРХ С ОДНОГО РАЗВЕТВЛЕНИЯ НА ДРУГОЕ,
 ТО ЕГО МОЖНО ЗАМЕНИТЬ ИГРОКОМ, КОТОРЫЙ В КОНЦЕ КОНЦОВ ВСЕ РАВНО ДОЛЖЕН 
ПОДНЯТЬСЯ, НА ЕГО ПРЕЖНЕЕ МЕСТО (А ИМЕННО НАИБОЛЬШИМ ИЗ ДВУХ КЛЮЧЕЙ, 
РАСПОЛОЖЕННЫХ ПОД НИМ). тЫПОЛНИВ ЭТУ ОПЕРАЦИЮ СТОЛЬКО РАЗ, СКОЛЬКО 
ВОЗМОЖНО, ПРИДЕМ ОТ РИС.~23(А) К РИС.~24.

ъОЛЬ СКОРО ДЕРЕВО ПОСТРОЕНО ТАКИМ ОБРАЗОМ, МОЖНО ПРОДОЛЖАТЬ СОРТИРОВКУ 
НЕ "ВОСХОДЯЩИМ" МЕТОДОМ, ПОКАЗАННЫМ НА РИС.~23, А "НИСХОДЯЩИМ": ВЫВОДИТСЯ 
ЭЛЕМЕНТ, НАХОДЯЩИЙСЯ
%% 176
В КОРНЕ, ПЕРЕМЕЩАЕТСЯ ВВЕРХ НАИБОЛЬШИЙ ИЗ ЕГО ПОТОМКОВ, ПЕРЕМЕЩАЕТСЯ ВВЕРХ 
НАИБОЛЬШИЙ ИЗ ПОТОМКОВ ПОСЛЕДНЕГО И Т. Д. яРОЦЕСС НАЧИНАЕТ ПОХОДИТЬ НЕ 
СТОЛЬКО НА ТУРНИР ПО НАСТОЛЬНОМУ ТЕННИСУ, СКОЛЬКО НА КОРПОРАТИВНУЮ СИСТЕМУ ВЫДВИЖЕНИЙ.

ўИТАТЕЛЬ ДОЛЖЕН УЯСНИТЬ, ЧТО У НИСХОДЯЩЕГО МЕТОДА ЕСТЬ ВАЖНОЕ 
ДОСТОИНСТВО---ОН ПОЗВОЛЯЕТ ИЗБЕЖАТЬ ЛИШНИХ СРАВНЕНИЙ $-\infty$ С~$-\infty$. 
(яОЛЬЗУЯСЬ ВОСХОДЯЩИМ МЕТОДОМ, МЫ НА БОЛЕЕ ПОЗДНИХ СТАДИЯХ СОРТИРОВКИ 
ВСЮДУ НАТЫКАЕМСЯ НА $-\infty$, А ПРИ НИСХОДЯЩЕМ МЕТОДЕ МОЖНО НА КАЖДОЙ 
СТАДИИ ЗАКАНЧИВАТЬ ПРЕОБРАЗОВАНИЕ ДЕРЕВА СРАЗУ ЖЕ ПОСЛЕ ЗАНЕСЕНИЯ $-\infty$.)
\picture{ЁИС. 25. яОСЛЕДОВАТЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ ДЛЯ 
ПОЛНОГО БИНАРНОГО ДЕРЕВА.}

эА РИС.~23 И~24 ИЗОБРАЖЕНЫ \emph{ПОЛНЫЕ БИНАРНЫЕ ДЕРЕВЬЯ} С 16 КОНЦЕВЫМИ 
УЗЛАМИ (СР. С П.~2.3.4.5); ТАКИЕ ДЕРЕВЬЯ УДОБНО ХРАНИТЬ В 
ПОСЛЕДОВАТЕЛЬНЫХ ЯЧЕЙКАХ ПАМЯТИ, КАК ПОКАЗАНО НА РИС.~25. чАМЕТИМ, ЧТО 
ОТЦОМ УЗЛА НОМЕР $k$ ЯВЛЯЕТСЯ УЗЕЛ $\lfloor k/2\rfloor$ , А ЕГО ПОТОМКАМИ 
ЯВЛЯЮТСЯ УЗЛЫ $2k$ И $2k+1$. юТСЮДА ВЫТЕКАЕТ ЕЩЕ ОДНО ПРЕИМУЩЕСТВО 
НИСХОДЯЩЕГО МЕТОДА, ПОСКОЛЬКУ ЗАЧАСТУЮ ЗНАЧИТЕЛЬНО ПРОЩЕ ПРОДВИГАТЬСЯ ВНИЗ 
ОТ УЗЛА $k$ К УЗЛАМ $2k$ И~$2k+1$, ЧЕМ ВВЕРХ ОТ УЗЛА $k$ К УЗЛАМ $k\oplus 
1$ 
И~$\lfloor k/2\rfloor$. (чДЕСЬ ЧЕРЕЗ $k\oplus 1$ ОБОЗНАЧЕНО ЧИСЛО $k+1$ 
ИЛИ $k-1$ В ЗАВИСИМОСТИ ОТ  ТОГО, ЯВЛЯЕТСЯ ЛИ $k$ ЧЕТНЫМ ИЛИ НЕЧЕТНЫМ.)

фО СИХ ПОР В НАШИХ ПРИМЕРАХ ВЫБОРА ИЗ ДЕРЕВА В ТОЙ ИЛИ ИНОЙ МЕРЕ 
ПРЕДПОЛАГАЛОСЬ, ЧТО $N$ ЕСТЬ СТЕПЕНЬ 2; В ДЕЙСТВИТЕЛЬНОСТИ МОЖНО 
РАБОТАТЬ С ПРОИЗВОЛЬНЫМ ЗНАЧЕНИЕМ $N$, ТАК КАК ПОЛНОЕ БИНАРНОЕ ДЕРЕВО С 
$N$ КОНЦЕВЫМИ УЗЛАМИ НЕТРУДНО ПОСТРОИТЬ ДЛЯ ЛЮБОГО N. 

 ьЫ ПОДОШЛИ ТЕПЕРЬ К ОСНОВНОМУ ВОПРОСУ: НЕЛЬЗЯ ЛИ В НИСХОДЯЩЕМ МЕТОДЕ 
ОБОЙТИСЬ СОВСЕМ БЕЗ "$-\infty$"? эЕ ПРАВДА ЛИ, БЫЛО БЫ ЧУДЕСНО, ЕСЛИ БЫ 
ВСЮ СУЩЕСТВЕННУЮ ИНФОРМАЦИЮ, ИМЕЮЩУЮСЯ НА РИС.~24, УДАЛОСЬ РАСПОЛОЖИТЬ В 
ЯЧЕЙКАХ 1--16
%%177
ПОЛНОГО БИНАРНОГО ДЕРЕВА БЕЗ ВСЯКИХ БЕСПОЛЕЗНЫХ "ДЫР", СОДЕРЖАЩИХ 
$-\infty$? яОРАЗМЫСЛИВ, МОЖНО ПРИЙТИ К ВЫВОДУ, ЧТО ЭТА ЦЕЛЬ В 
ДЕЙСТВИТЕЛЬНОСТИ ДОСТИЖИМА, ПРИЧЕМ НЕ ТОЛЬКО ИСКЛЮЧАЕТСЯ $-\infty$, НО И 
ПОЯВЛЯЕТСЯ ВОЗМОЖНОСТЬ СОРТИРОВАТЬ $N$ ЗАПИСЕЙ НА ТОМ ЖЕ МЕСТЕ БЕЗ 
ВСПОМОГАТЕЛЬНОЙ ОБЛАСТИ ВЫВОДА. ¤ТО ПРИВОДИТ К ЕЩЕ ОДНОМУ ВАЖНОМУ 
АЛГОРИТМУ СОРТИРОВКИ. хГО АВТОР фЖ.~є.~фЖ.~єИЛЬЯМС [{\sl CACM\/}, {\bf 7} 
(1964), 347--348] ОКРЕСТИЛ СВОЙ АЛГОРИТМ "ПИРАМИДАЛЬНОЙ-СОРТИРОВКОЙ" ("heapsort").

\section яИРАМИДАЛЬНАЯ СОРТИРОВКА.  сУДЕМ НАЗЫВАТЬ ФАЙЛ КЛЮЧЕЙ $K_1$, 
$K_2$, \dots, $K_N$ "ПИРАМИДОЙ", ЕСЛИ
$$
K_{\lfloor j/2\rfloor}\ge K_j \rem{ ПРИ $1\le \lfloor j/2\rfloor<j\le N$.}
\eqno(3)
$$
т ЭТОМ СЛУЧАЕ $K_1\ge K_2$, $K_1\ge K_3$, $K_2\ge K_4$ И Т.Д.; ИМЕННО ЭТО 
УСЛОВИЕ ВЫПОЛНЯЕТСЯ НА РИС.~24. шЗ НЕГО СЛЕДУЕТ, В ЧАСТНОСТИ, ЧТО 
НАИБОЛЬШИЙ КЛЮЧ ОКАЗЫВАЕТСЯ "НА ВЕРШИНЕ ПИРАМИДЫ":
$$
K_1=\max(K_1, K_2, \ldots, K_N).
\eqno(4)
$$
хСЛИ БЫ МЫ СУМЕЛИ КАК-НИБУДЬ ПРЕОБРАЗОВАТЬ ПРОИЗВОЛЬНЫЙ ИСХОДНЫЙ ФАЙЛ В 
ПИРАМИДУ, ТО ДЛЯ ПОЛУЧЕНИЯ ЭФФЕКТИВНОГО АЛГОРИТМА СОРТИРОВКИ МОЖНО БЫЛО БЫ 
ВОСПОЛЬЗОВАТЬСЯ "НИСХОДЯЩЕЙ" ПРОЦЕДУРОЙ ВЫБОРА, ПОДОБНОЙ ТОЙ, КОТОРАЯ 
ОПИСАНА ВЫШЕ.

¤ФФЕКТИВНЫЙ ПОДХОД К ЗАДАЧЕ ПОСТРОЕНИЯ ПИРАМИДЫ ПРЕДЛОЖИЛ Ё.~є.~ЇЛОЙД 
[{\sl CACM\/}, {\bf 7} (1964), 701]. яУСТЬ НАМ УДАЛОСЬ РАСПОЛОЖИТЬ ФАЙЛ 
ТАКИМ ОБРАЗОМ, ЧТО
$$
K_{\lfloor j/2\rfloor}\ge K_j \rem{ ПРИ $l < \lfloor j/2\rfloor<j\le N$,}
\eqno(5)
$$
ГДЕ $l$---НЕКОТОРОЕ ЧИСЛО $\ge1$. (т ИСХОДНОМ ФАЙЛЕ ЭТО УСЛОВИЕ ВЫПОЛНЯЕТСЯ 
"АВТОМАТИЧЕСКИ" ДЛЯ $l=\floor{N/2}$, ПОСКОЛЬКУ НИ ОДИН ИНДЕКС $j$ НЕ 
УДОВЛЕТВОРЯЕТ УСЛОВИЮ $\floor{N/2}<\floor{j/2}<j\le N$.) 
эЕТРУДНО ПОНЯТЬ, КАК, ИЗМЕНЯЯ ЛИШЬ ПОДДЕРЕВО С КОРНЕМ В УЗЛЕ $l$, 
ПРЕОБРАЗОВАТЬ ФАЙЛ, ЧТОБЫ РАСПРОСТРАНИТЬ НЕРАВЕНСТВА (5) И НА СЛУЧАЙ, 
КОГДА $\floor{j/2}=l$. ёЛЕДОВАТЕЛЬНО, МОЖНО УМЕНЬШАТЬ $l$ НА ЕДИНИЦУ, ПОКА В 
КОНЦЕ КОНЦОВ НЕ БУДЕТ ДОСТИГНУТО УСЛОВИЕ (3). ¤ТИ ИДЕИ єИЛЬЯМСА И ЇЛОЙДА 
ПРИВОДЯТ К ИЗЯЩНОМУ АЛГОРИТМУ, КОТОРЫЙ ЗАСЛУЖИВАЕТ ПРИСТАЛЬНОГО ИЗУЧЕНИЯ.

\alg H.(яИРАМИДАЛЬНАЯ СОРТИРОВКА.) чАПИСИ $R_1$, \dots, 
$R_N$ ПЕРЕРАЗМЕЩАЮТСЯ НА ТОМ ЖЕ МЕСТЕ; ПОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ ИХ 
КЛЮЧИ БУДУТ УПОРЯДОЧЕНЫ: $K_1\le \ldots \le K_N$. ёНАЧАЛА 
ФАЙЛ ПЕРЕСТРАИВАЕТСЯ В ПИРАМИДУ, ПОСЛЕ ЧЕГО ВЕРШИНА ПИРАМИДЫ МНОГОКРАТНО 
ИСКЛЮЧАЕТСЯ И ЗАПИСЫВАЕТСЯ НА СВОЕ ОКОНЧАТЕЛЬНОЕ МЕСТО. яРЕДПОЛАГАЕТСЯ, 
ЧТО $N\ge2$.
\st[эАЧАЛЬНАЯ УСТАНОВКА.] єСТАНОВИТЬ $l\asg\floor{N/2}+1$, $r\asg N$.
\st[єМЕНЬШИТЬ $l$ ИЛИ~$r$.] хСЛИ. $l>1$, ТО УСТАНОВИТЬ $l\asg l-1$, $R\asg 
R_l$, $K\asg K_l$. (хСЛИ  $l>1$, ЭТО ОЗНАЧАЕТ, ЧТО ПРОИСХОДИТ
%% 178
ПРОЦЕСС ПРЕОБРАЗОВАНИЯ ИСХОДНОГО ФАЙЛА В ПИРАМИДУ; ЕСЛИ ЖЕ $l= 1$, ТО ЭТО 
ЗНАЧИТ, ЧТО КЛЮЧИ $K_1$, $K_2$, \dots, $K_r$ УЖЕ ОБРАЗУЮТ ПИРАМИДУ.) т 
ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ $R\asg R_r$, $K\asg K_r$, $R_r\asg R_1$  И 
$r\asg r-1$; ЕСЛИ В РЕЗУЛЬТАТЕ ОКАЗАЛОСЬ, ЧТО $r=1$, ТО УСТАНОВИТЬ 
$R_1\asg R$ И ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА.

\st[яРИГОТОВИТЬСЯ К "ПРОТАСКИВАНИЮ".] єСТАНОВИТЬ $j\asg l$. 
(ъ ЭТОМУ МОМЕНТУ
$$
K_\floor{j/2}\ge K_j \rem{ПРИ $l<\floor{j/2}<j\le r$,}
\eqno(6)
$$
А ЗАПИСИ $R_k$, $r<k\le N$, ЗАНИМАЮТ СВОИ ОКОНЧАТЕЛЬНЫЕ МЕСТА. °АГИ 
\stp{3}--\stp{8} НАЗЫВАЮТСЯ АЛГОРИТМОМ "ПРОТАСКИВАНИЯ"; ИХ
\picture{ЁИС. 26. яИРАМИДАЛЬНАЯ СОРТИРОВКА; ПУНКТИРОМ ОБВЕДЕН АЛГОРИТМ "ПРОТАСКИВАНИЯ".}
ДЕЙСТВИЕ ЭКВИВАЛЕНТНО УСТАНОВКЕ $R_l\asg R$ С ПОСЛЕДУЮЩИМ ПЕРЕМЕЩЕНИЕМ 
ЗАПИСЕЙ $R_l$, \dots, $R_r$ ТАКИМ ОБРАЗОМ, ЧТОБЫ УСЛОВИЕ (6) ВЫПОЛНЯЛОСЬ И 
ПРИ $\floor{j/2}=l$.)

\st[яРОДВИНУТЬСЯ ВНИЗ.] єСТАНОВИТЬ $i\asg j$ И $j\asg 2j$. (т ПОСЛЕДУЮЩИХ 
ШАГАХ $i = \floor{j/2}$.) хСЛИ $j< r$, ТО ПЕРЕЙТИ К ШАГУ \stp{5};
ЕСЛИ $j=r$, ТО ПЕРЕЙТИ К ШАГУ \stp{6}; ЕСЛИ ЖЕ $j>r$, ТО ПЕРЕЙТИ К ШАГУ \stp{8}.

\st[эАЙТИ "БОЛЬШЕГО" СЫНА.] хСЛИ $K_j<K_{j+1}$, ТО УСТАНОВИТЬ
$j\asg j+1$.

\st[сОЛЬШЕ $K$?] хСЛИ $K\ge K_j$, ТО ПЕРЕЙТИ К ШАГУ \stp{8}. 
\st[яОДНЯТЬ ЕГО ВВЕРХ.] єСТАНОВИТЬ $R_i\asg R_j$ И ВОЗВРАТИТЬСЯ
К ШАГУ \stp{4}.

\st[чАНЕСТИ $R$.] єСТАНОВИТЬ $R_i\asg R$. (эА ЭТОМ АЛГОРИТМ 
"ПРОТАСКИВАНИЯ", НАЧАТЫЙ В ШАГЕ \stp{ч}, ЗАКАНЧИВАЕТСЯ.) тОЗВРАТИТЬСЯ 
К ШАГУ \stp{2}.
\algend
%%179
\bye