\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