\input style
%% 181
$7A+14B+4C+20N-2D+15\lfloor N/2 \rfloor -28$ РАВНО, ТАКИМ ОБРАЗОМ, В 
СРЕДНЕМ ПРИМЕРНО $16N \log_2 N+0.2N$ ЕДИНИЦ.

гЛЯДЯ НА ТАБЛ.~2, ТРУДНО ПОВЕРИТЬ В ТО, ЧТО ПИРАМИДАЛЬНАЯ СОРТИРОВКА ТАК 
УЖ ЭФФЕКТИВНА: БОЛЬШИЕ КЛЮЧИ ПЕРЕМЕЩАЮТСЯ ВЛЕВО ПРЕЖДЕ, ЧЕМ МЫ УСПЕВАЕМ 
ОТЛОЖИТЬ ИХ ВПРАВО! эТО И В САМОМ ДЕЛЕ СТРАННЫЙ СПОСОБ СОРТИРОВКИ ПРИ 
МАЛЫХ $N$. вРЕМЯ СОРТИРОВКИ 16 КЛЮЧЕЙ ИЗ ТАБЛ.~2 РАВНО $1068u$, ТОГДА КАК 
ОБЫЧНЫЙ МЕТОД ПРОСТЫХ ВСТАВОК (ПРОГРАММА 5.2.1S) ТРЕБУЕТ ВСЕГО 
$514u$. пРИ СОРТИРОВКЕ ПРОСТЫМ ВЫБОРОМ (ПРОГРАММА S) ТРЕБУЕТСЯ $853u$.

пРИ БОЛЬШИХ $N$ ПРОГРАММА H БОЛЕЕ ЭФФЕКТИВНА. нАПРАШИВАЕТСЯ СРАВНЕНИЕ С 
СОРТИРОВКОЙ МЕТОДОМ шЕЛЛА С УБЫВАЮЩИМ ШАГОМ (ПРОГРАММА 5.2.1D) И БЫСТРОЙ 
СОРТИРОВКОЙ хОАРА (ПРОГРАММА 5.2.2Q), ТАК КАК ВО ВСЕХ ТРЕХ ПРОГРАММАХ 
СОРТИРОВКА ПРОИЗВОДИТСЯ ПУТЕМ СРАВНЕНИЯ КЛЮЧЕЙ, ПРИЧЕМ 
ВСПОМОГАТЕЛЬНОЙ ПАМЯТИ ИСПОЛЬЗУЕТСЯ МАЛО ИЛИ ОНА НЕ ИСПОЛЬЗУЕТСЯ ВОВСЕ. 
пРИ $N=1000$ СРЕДНИЕ ВРЕМЕНА РАБОТЫ РАВНЫ ПРИБЛИЗИТЕЛЬНО
$$
\eqalign{
160000u & \hbox{ ДЛЯ ПИРАМИДАЛЬНОЙ СОРТИРОВКИ;}\cr
130000u & \hbox{ ДЛЯ СОРТИРОВКИ МЕТОДОМ шЕЛЛА;}\cr
  80000u  &\hbox{ ДЛЯ БЫСТРОЙ СОРТИРОВКИ.}\cr
}
$$
(\MIX---ТИПИЧНЫЙ ПРЕДСТАВИТЕЛЬ БОЛЬШИНСТВА СОВРЕМЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ 
МАШИН, НО, РАЗУМЕЕТСЯ, НА КОНКРЕТНЫХ МАШИНАХ ПОЛУЧАТСЯ НЕСКОЛЬКО ИНЫЕ 
ОТНОСИТЕЛЬНЫЕ ВЕЛИЧИНЫ.) с РОСТОМ $N$ ПИРАМИДАЛЬНАЯ СОРТИРОВКА ПРЕВЗОЙДЕТ 
ПО СКОРОСТИ МЕТОД шЕЛЛА, НО АСИМПТОТИЧЕСКАЯ ФОРМУЛА $16N\log_2 N \approx  
23.08N\ln N$ НИКОГДА НЕ СТАНЕТ ЛУЧШЕ ВЫРАЖЕНИЯ ДЛЯ БЫСТРОЙ СОРТИРОВКИ 
$12.67N \ln N$. мОДИФИКАЦИЯ ПИРАМИДАЛЬНОЙ СОРТИРОВКИ, ОБСУЖДАЕМАЯ В 
УПР.~18, УСКОРИТ ПРОЦЕСС НА МНОГИХ ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ, НО ДАЖЕ С ЭТИМ 
УСОВЕРШЕНСТВОВАНИЕМ ПИРАМИДАЛЬНАЯ СОРТИРОВКА НЕ ДОСТИГНЕТ СКОРОСТИ БЫСТРОЙ СОРТИРОВКИ.

с ДРУГОЙ СТОРОНЫ, БЫСТРАЯ СОРТИРОВКА ЭФФЕКТИВНА ЛИШЬ В СРЕДНЕМ; В 
НАИХУДШЕМ СЛУЧАЕ ЕЕ ВРЕМЯ РАБОТЫ ПРОПОРЦИОНАЛЬНО $N^2$. пИРАМИДАЛЬНАЯ ЖЕ 
СОРТИРОВКА ОБЛАДАЕТ ТЕМ ИНТЕРЕСНЫМ СВОЙСТВОМ, ЧТО ДЛЯ НЕЕ НАИХУДШИЙ 
СЛУЧАЙ НЕ НАМНОГО ХУЖЕ СРЕДНЕГО. вСЕГДА ВЫПОЛНЯЮТСЯ НЕРАВЕНСТВА
$$
A\le 1.5 N, \quad B \le N \lfloor \log_2 N \rfloor, 
\quad C\le N\lfloor \log_2 N\rfloor;
\eqno (8)
$$
ТАКИМ ОБРАЗОМ, НЕЗАВИСИМО ОТ РАСПРЕДЕЛЕНИЯ ИСХОДНЫХ ДАННЫХ ВЫПОЛНЕНИЕ 
ПРОГРАММЫ H НЕ ЗАЙМЕТ БОЛЕЕ 
$18N \lfloor \log_2 N\rfloor+38N$
ЕДИНИЦ ВРЕМЕНИ. пИРАМИДАЛЬНАЯ СОРТИРОВКА---ПЕРВЫЙ ИЗ РАССМОТРЕННЫХ НАМИ ДО 
СИХ ПОР МЕТОДОВ СОРТИРОВКИ, ВРЕМЯ РАБОТЫ КОТОРОГО \emph{ЗАВЕДОМО} ИМЕЕТ 
ПОРЯДОК $N\log N$. сОРТИРОВКА ПОСРЕДСТВОМ СЛИЯНИЙ, КОТОРАЯ БУДЕТ 
ОБСУЖДАТЬСЯ НИЖЕ, В П.~5.2.4, ТОЖЕ ОБЛАДАЕТ ЭТИМ СВОЙСТВОМ, НО ОНА ТРЕБУЕТ 
БОЛЬШЕ ПАМЯТИ.

%% 182

\section нАИБОЛЬШИЙ ИЗ ВКЛЮЧЕННЫХ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ. 
в ГЛ. 2 МЫ
ВИДЕЛИ, ЧТО ЛИНЕЙНЫЕ СПИСКИ ЧАСТО МОЖНО ОСМЫСЛЕННО РАСКЛАССИФИЦИРОВАТЬ 
ПО ХАРАКТЕРУ ПРОИЗВОДИМЫХ НАД НИМИ ОПЕРАЦИЙ ВКЛЮЧЕНИЯ И ИСКЛЮЧЕНИЯ. 
\emph{сТЕК} ВЕДЕТ СЕБЯ ПО ПРИНЦИПУ "ПОСЛЕДНИМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ 
ИСКЛЮЧАЕТСЯ" В ТОМ СМЫСЛЕ, ЧТО ПРИ КАЖДОМ ИСКЛЮЧЕНИИ УДАЛЯЕТСЯ САМЫЙ 
МОЛОДОЙ ЭЛЕМЕНТ СПИСКА (ЭЛЕМЕНТ, КОТОРЫЙ БЫЛ ВСТАВЛЕН ПОЗЖЕ ВСЕХ ДРУГИХ 
ЭЛЕМЕНТОВ, ПРИСУТСТВУЮЩИХ В ДАННЫЙ МОМЕНТ В СПИСКЕ). пРОСТАЯ 
\emph{ОЧЕРЕДЬ} ВЕДЕТ СЕБЯ ПО ПРИНЦИПУ "ПЕРВЫМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ 
ИСКЛЮЧАЕТСЯ" В ТОМ СМЫСЛЕ, ЧТО ПРИ КАЖДОМ ИСКЛЮЧЕНИИ УДАЛЯЕТСЯ САМЫЙ 
СТАРШИЙ ИЗ ИМЕЮЩИХСЯ ЭЛЕМЕНТОВ. в БОЛЕЕ СЛОЖНЫХ СИТУАЦИЯХ, ТАКИХ, КАК 
МОДЕЛИРОВАНИЕ ЛИФТА В П.~2.2.5, ТРЕБУЕТСЯ СПИСОК ТИПА "НАИМЕНЬШИЙ ИЗ 
ВКЛЮЧЕННЫХ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ", ГДЕ ПРИ КАЖДОМ ИСКЛЮЧЕНИИ УДАЛЯЕТСЯ 
ЭЛЕМЕНТ, ИМЕЮЩИЙ НАИМЕНЬШИЙ КЛЮЧ. тАКОЙ СПИСОК МОЖНО 
НАЗВАТЬ \dfn{ПРИОРИТЕТНОЙ ОЧЕРЕДЬЮ}, ТАК КАК КЛЮЧ КАЖДОГО ЭЛЕМЕНТА 
ОТРАЖАЕТ ЕГО ОТНОСИТЕЛЬНУЮ СПОСОБНОСТЬ БЫСТРО ПОКИНУТЬ 
СПИСОК. сОРТИРОВКА ПОСРЕДСТВОМ ВЫБОРА---ЧАСТНЫЙ СЛУЧАЙ ПРИОРИТЕТНОЙ ОЧЕРЕДИ, 
НАД КОТОРОЙ ПРОИЗВОДИТСЯ СНАЧАЛА $N$ ОПЕРАЦИЙ ВСТАВКИ, А ЗАТЕМ $N$ 
ОПЕРАЦИЙ УДАЛЕНИЯ.

пРИОРИТЕТНЫЕ ОЧЕРЕДИ ВОЗНИКАЮТ В САМЫХ РАЗНООБРАЗНЫХ ПРИЛОЖЕНИЯХ. нАПРИМЕР,
 В НЕКОТОРЫХ ЧИСЛЕННЫХ ИТЕРАТИВНЫХ СХЕМАХ ПОВТОРЯЕТСЯ ВЫБОР ЭЛЕМЕНТА, 
ИМЕЮЩЕГО НАИБОЛЬШЕЕ (ИЛИ НАИМЕНЬШЕЕ) ЗНАЧЕНИЕ НЕКОТОРОГО ПРОВЕРОЧНОГО 
КРИТЕРИЯ; ПАРАМЕТРЫ ВЫБРАННОГО ЭЛЕМЕНТА ИЗМЕНЯЮТСЯ, И ОН СНОВА 
ВСТАВЛЯЕТСЯ В СПИСОК С НОВЫМ ПРОВЕРОЧНЫМ ЗНАЧЕНИЕМ,- СООТВЕТСТВУЮЩИМ НОВЫМ 
ЗНАЧЕНИЯМ ПАРАМЕТРОВ. пРИОРИТЕТНЫЕ ОЧЕРЕДИ ЧАСТО ИСПОЛЬЗУЮТСЯ В 
ОПЕРАЦИОННЫХ СИСТЕМАХ ПРИ ПЛАНИРОВАНИИ ЗАДАНИЙ. дРУГИЕ ТИПИЧНЫЕ 
ПРИМЕНЕНИЯ ПРИОРИТЕТНЫХ ОЧЕРЕДЕЙ УПОМИНАЮТСЯ В УПР.~15, 29 И~36; КРОМЕ 
ТОГО, МНОГО ПРИМЕРОВ ВСТРЕТИТСЯ В ПОСЛЕДУЮЩИХ ГЛАВАХ.

кАК ЖЕ РЕАЛИЗОВАТЬ ПРИОРИТЕТНУЮ ОЧЕРЕДЬ? оДИН ИЗ ОЧЕВИДНЫХ 
СПОСОБОВ---ПОДДЕРЖИВАТЬ ОТСОРТИРОВАННЫЙ СПИСОК ЭЛЕМЕНТОВ, УПОРЯДОЧЕННЫХ ПО. 
КЛЮЧАМ. тОГДА ВКЛЮЧЕНИЕ НОВОГО ЭЛЕМЕНТА, ПО СУЩЕСТВУ, СВОДИТСЯ К ЗАДАЧЕ, 
РАССМОТРЕННОЙ НАМИ ПРИ ИЗУЧЕНИИ СОРТИРОВКИ ВСТАВКАМИ В П.~5.2.1. пРИ 
ДРУГОМ, ЕЩЕ БОЛЕЕ ОЧЕВИДНОМ СПОСОБЕ РАБОТЫ С ПРИОРИТЕТНОЙ ОЧЕРЕДЬЮ 
ЭЛЕМЕНТЫ В СПИСКЕ ХРАНЯТСЯ В ПРОИЗВОЛЬНОМ ПОРЯДКЕ, И ТОГДА ДЛЯ 
ВЫБОРА НУЖНОГО ЭЛЕМЕНТА, ПРИХОДИТСЯ ОСУЩЕСТВЛЯТЬ ПОИСК НАИБОЛЬШЕГО (ИЛИ 
НАИМЕНЬШЕГО) КЛЮЧА КАЖДЫЙ РАЗ, КОГДА НЕОБХОДИМО ПРОИЗВЕСТИ ИСКЛЮЧЕНИЕ. в 
ОБОИХ ЭТИХ ОЧЕВИДНЫХ ПОДХОДАХ НЕПРИЯТНОСТЬ СОСТОИТ В ТОМ, ЧТО ТРЕБУЕТСЯ 
ПОРЯДКА $N$ ШАГОВ ДЛЯ ВЫПОЛНЕНИЯ ЛИБО ОПЕРАЦИИ ВСТАВКИ, ЛИБО ОПЕРАЦИИ 
УДАЛЕНИЯ, ЕСЛИ В СПИСКЕ СОДЕРЖИТСЯ $N$ ЭЛЕМЕНТОВ, Т. Е. ПРИ БОЛЬШИХ $N$ 
ЭТИ ОПЕРАЦИИ ЗАНИМАЮТ СЛИШКОМ МНОГО ВРЕМЕНИ.

в СВОЕЙ СТАТЬЕ О ПИРАМИДАЛЬНОЙ СОРТИРОВКЕ уИЛЬЯМЕ УКАЗАЛ
%% 183
НА ТО, ЧТО ПИРАМИДЫ ИДЕАЛЬНО ПОДХОДЯТ ДЛЯ ПРИЛОЖЕНИЙ С БОЛЬШИМИ 
ПРИОРИТЕТНЫМИ ОЧЕРЕДЯМИ, ТАК КАК ЭЛЕМЕНТ МОЖНО ВСТАВИТЬ В ПИРАМИДУ ИЛИ 
УДАЛИТЬ ИЗ НЕЕ ЗА $O(\log N)$ ШАГОВ; К ТОМУ ЖЕ ВСЕ ЭЛЕМЕНТЫ ПИРАМИДЫ 
КОМПАКТНО РАСПОЛАГАЮТСЯ В ПОСЛЕДОВАТЕЛЬНЫХ ЯЧЕЙКАХ ПАМЯТИ. фАЗА ВЫБОРА В 
АЛГОРИТМЕ H---ЭТО ПОСЛЕДОВАТЕЛЬНОСТЬ ШАГОВ УДАЛЕНИЯ В ПРОЦЕССЕ ТИПА 
\emph{НАИБОЛЬШИЙ ИЗ ВКЛЮЧЕННЫХ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ}: ЧТОБЫ ИСКЛЮЧИТЬ 
НАИБОЛЬШИЙ ЭЛЕМЕНТ $K_1$ МЫ УДАЛЯЕМ ЕГО И "ПРОТАСКИВАЕМ" ЭЛЕМЕНТ $K_N$ В 
НОВОЙ ПИРАМИДЕ ИЗ $N-1$ ЭЛЕМЕНТОВ. (еСЛИ НУЖЕН АЛГОРИТМ ТИПА 
\emph{НАИМЕНЬШИЙ ИЗ ВКЛЮЧЕННЫХ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ}, КАК ПРИ МОДЕЛИРОВАНИИ 
ЛИФТА, ТО, ОЧЕВИДНО, МОЖНО ИЗМЕНИТЬ ОПРЕДЕЛЕНИЕ ПИРАМИДЫ, ЗАМЕНИВ В (3) 
ЗНАК "$\ge$" НА "$\le$"; ДЛЯ УДОБСТВА МЫ БУДЕМ РАССМАТРИВАТЬ ЗДЕСЬ ЛИШЬ 
СЛУЧАЙ "НАИБОЛЬШИЙ ИЗ ВКЛЮЧЕННЫХ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ".) вООБЩЕ, ЕСЛИ 
ТРЕБУЕТСЯ ИСКЛЮЧИТЬ НАИБОЛЬШИЙ ЭЛЕМЕНТ, А ЗАТЕМ ВСТАВИТЬ НОВЫЙ ЭЛЕМЕНТ 
$x$, ТО МОЖНО ВЫПОЛНИТЬ ПРОЦЕДУРУ ПРОТАСКИВАНИЯ С $l=1$, $r=N$ И $K=x$. 
еСЛИ ЖЕ НЕОБХОДИМО ВСТАВИТЬ ЭЛЕМЕНТ БЕЗ ПРЕДВАРИТЕЛЬНОГО ИСКЛЮЧЕНИЯ, ТО 
МОЖНО ВОСПОЛЬЗОВАТЬСЯ "ВОСХОДЯЩЕЙ" ПРОЦЕДУРОЙ ИЗ УПР. 16.

\section сВЯЗАННОЕ ПРЕДСТАВЛЕНИЕ ПРИОРИТЕТНЫХ ОЧЕРЕДЕЙ. 
эФФЕКТИВНЫЙ СПОСОБ ПРЕДСТАВЛЕНИЯ ПРИОРИТЕТНЫХ ОЧЕРЕДЕЙ В ВИДЕ 
СВЯЗАННЫХ БИНАРНЫХ ДЕРЕВЬЕВ ПРЕДЛОЖИЛ В 1971~Г. кЛАРК~э.~кРЭЙН. еГО МЕТОД 
ТРЕБУЕТ НАЛИЧИЯ В КАЖДОЙ ЗАПИСИ ДВУХ ПОЛЕЙ СВЯЗИ И КОРОТКОГО ПОЛЯ 
СЧЕТЧИКА, НО ПО СРАВНЕНИЮ С ПИРАМИДАМИ ОН ОБЛАДАЕТ СЛЕДУЮЩИМИ ПРЕИМУЩЕСТВАМИ:
\enumerate
\li еСЛИ С ПРИОРИТЕТНОЙ ОЧЕРЕДЬЮ РАБОТАЮТ КАК СО СТЕКОМ, ТО ОПЕРАЦИИ 
ВКЛЮЧЕНИЯ И ИСКЛЮЧЕНИЯ БОЛЕЕ ЭФФЕКТИВНЫ (ОНИ ЗАНИМАЮТ ФИКСИРОВАННОЕ ВРЕМЯ, 
НЕ ЗАВИСЯЩЕЕ ОТ ДЛИНЫ ОЧЕРЕДИ).

\li зАПИСИ НИКОГДА НЕ ПЕРЕМЕЩАЮТСЯ, ИЗМЕНЯЮТСЯ ТОЛЬКО УКАЗАТЕЛИ.

\li  мОЖНО СЛИТЬ ДВЕ НЕПЕРЕСЕКАЮЩИЕСЯ ПРИОРИТЕТНЫЕ ОЧЕРЕДИ, СОДЕРЖАЩИЕ В 
ОБЩЕЙ СЛОЖНОСТИ $N$ ЭЛЕМЕНТОВ, В ОДНУ ВСЕГО ЗА $O (\log N)$ ШАГОВ.
\enumend

сЛЕГКА ВИДОИЗМЕНЕННЫЙ МЕТОД кРЭЙНА ПРОИЛЛЮСТРИРОВАН НА РИС.~27, НА КОТОРОМ 
ПОКАЗАН ОСОБЫЙ ТИП СТРУКТУРЫ БИНАРНОГО ДЕРЕВА. кАЖДЫЙ УЗЕЛ СОДЕРЖИТ ПОЛЕ 
|KEY|, ПОЛЕ |DIST| И ДВА ПОЛЯ СВЯЗИ---|LEFT| И |RIGHT|. пОЛЕ |DIST| ВСЕГДА 
УСТАНАВЛИВАЕТСЯ РАВНЫМ ДЛИНЕ КРАТЧАЙШЕГО ПУТИ ОТ ЭТОГО УЗЛА ДО 
КОНЦЕВОГО УЗЛА (Т. Е. ДО ПУСТОГО УЗЛА $\NULL$) ДЕРЕВА. еСЛИ СЧИТАТЬ, 
ЧТО $|DIST|(\NULL) = 0$ И~$|KEY|(\NULL) =-\infty$, ТО ПОЛЯ |KEY| И~|DIST| 
В ЭТОМ ДЕРЕВЕ УДОВЛЕТВОРЯЮТ СЛЕДУЮЩИМ СООТНОШЕНИЯМ:
$$
\displaylines{
\hfill|KEY| (|р|)\ge  |KEY| (|LEFT| (|P|)), |KEY| (|P|) \ge |KEY| (|RIGHT| 
(|P|));     \hfill\llap{(9)}\cr
\hfill|DIST| (|P|)=1+\min (|DIST| (|LEFT| (|P|)), |DIST| (|RIGHT| (|P|))); 
\hfill\llap{(10)}\cr
\hfill|DIST| (|LEFT| (|P|)) \ge  |DIST| (|RIGHT| (|P|)).\hfill\llap{(11)}\cr
}
$$
%%184
сООТНОШЕНИЕ (9) АНАЛОГИЧНО УСЛОВИЮ ПИРАМИДЫ (3) И СЛУЖИТ ГАРАНТИЕЙ ТОГО, 
ЧТО В КОРНЕ ДЕРЕВА НАХОДИТСЯ НАИБОЛЬШИЙ КЛЮЧ, А СООТНОШЕНИЕ (10)---ЭТО 
ПРОСТО ОПРЕДЕЛЕНИЕ ПОЛЯ |DIST|, СФОРМУЛИРОВАННОЕ ВЫШЕ. сООТНОШЕНИЕ (11) 
ПРЕДСТАВЛЯЕТ СОБОЙ ИНТЕРЕСНОЕ НОВШЕСТВО: ИЗ НЕГО СЛЕДУЕТ, ЧТО КРАТЧАЙШИЙ 
ПУТЬ К КОНЦЕВОМУ УЗЛУ ВСЕГДА МОЖНО ПОЛУЧИТЬ, ДВИГАЯСЬ ВПРАВО. мЫ
\picture{рИС. 27. пРИОРИТЕТНАЯ ОЧЕРЕДЬ, ПРЕДСТАВЛЕННАЯ В ВИДЕ 
ЛЕВОСТОРОННЕГО ДЕРЕВА.}
БУДЕМ НАЗЫВАТЬ БИНАРНОЕ ДЕРЕВО С ЭТИМ СВОЙСТВОМ ЛЕВОСТОРОННИМ ДЕРЕВОМ, 
ПОСКОЛЬКУ ОНО, КАК ПРАВИЛО, СИЛЬНО "ТЯНЕТСЯ" ВЛЕВО.

иЗ ЭТИХ ОПРЕДЕЛЕНИЙ ЯСНО, ЧТО РАВЕНСТВО $|DlST|(|P|)=n$ ПОДРАЗУМЕВАЕТ 
СУЩЕСТВОВАНИЕ ПО КРАЙНЕЙ МЕРЕ $2^n$ КОНЦЕВЫХ УЗЛОВ НИЖЕ |P|; В ПРОТИВНОМ 
СЛУЧАЕ НАШЕЛСЯ БЫ БОЛЕЕ, КОРОТКИЙ ПУТЬ ОТ |P| ДО КОНЦЕВОГО УЗЛА. тАКИМ 
ОБРАЗОМ, ЕСЛИ В ЛЕВОСТОРОННЕМ ДЕРЕВЕ ИМЕЕТСЯ $N$ УЗЛОВ, ТО ПУТЬ, ВЕДУЩИЙ 
ИЗ КОРНЯ ВНИЗ ПО НАПРАВЛЕНИЮ ВПРАВО, СОДЕРЖИТ НЕ БОЛЕЕ ЧЕМ $\lfloor 
\log_2(N+1)\rfloor$ УЗЛОВ. нОВЫЙ УЗЕЛ МОЖНО ВСТАВИТЬ В ПРИОРИТЕТНУЮ 
ОЧЕРЕДЬ, ПРОЙДЯ ПО ЭТОМУ ПУТИ (СМ. УПР.~32); СЛЕДОВАТЕЛЬНО, В 
ХУДШЕМ СЛУЧАЕ НЕОБХОДИМО ВСЕГО $O(\log N)$ ШАГОВ. нАИЛУЧШИЙ СЛУЧАЙ
%%185
ДОСТИГАЕТСЯ, КОГДА ДЕРЕВО ЛИНЕЙНО (ВСЕ СВЯЗИ |RIGHT| РАВНЫ $\NULL$), А 
НАИХУДШИЙ СЛУЧАЙ ДОСТИГАЕТСЯ, КОГДА ДЕРЕВО АБСОЛЮТНО СБАЛАНСИРОВАНО.

чТОБЫ УДАЛИТЬ УЗЕЛ ИЗ КОРНЯ, НУЖНО ПРОСТО СЛИТЬ ДВА ЕГО ПОДДЕРЕВА. 
оПЕРАЦИЯ СЛИЯНИЯ ДВУХ НЕПЕРЕСЕКАЮЩИХСЯ ЛЕВОСТОРОННИХ ДЕРЕВЬЕВ, НА 
КОТОРЫЕ ССЫЛАЮТСЯ УКАЗАТЕЛИ |P| И~|Q|, ПО СВОЕЙ ИДЕЕ ПРОСТА: ЕСЛИ 
$|KEY|(|P|)\ge |KEY| (|Q|)$, ТО БЕРЕМ В КАЧЕСТВЕ КОРНЯ |P| И СЛИВАЕМ |Q| С 
ПРАВЫМ ПОДДЕРЕВОМ |P|; ПРИ ЭТОМ ИЗМЕНИТСЯ $|DIST|(|P|)$, a $|LEFT|(|р|)$ 
МЕНЯЕТСЯ МЕСТАМИ С $|RIGHT|(|P|)$, ЕСЛИ ЭТО НЕОБХОДИМО. нЕТРУДНО СОСТАВИТЬ 
ПОДРОБНОЕ ОПИСАНИЕ ЭТОГО ПРОЦЕССА (СМ. УПР.~32).

\section сРАВНЕНИЕ МЕТОДОВ РАБОТЫ С ПРИОРИТЕТНЫМИ ОЧЕРЕДЯМИ. еСЛИ ЧИСЛО 
УЗЛОВ $N$ МАЛО, ТО ДЛЯ ПОДДЕРЖАНИЯ ПРИОРИТЕТНОЙ ОЧЕРЕДИ ЛУЧШЕ ВСЕГО 
ПРИМЕНЯТЬ ОДИН ИЗ ПРОСТЫХ МЕТОДОВ С ИСПОЛЬЗОВАНИЕМ ЛИНЕЙНЫХ СПИСКОВ. 
еСЛИ ЖЕ $N$ ВЕЛИКО, ТО, ОЧЕВИДНО, ГОРАЗДО БОЛЕЕ БЫСТРЫМ БУДЕТ МЕТОД, ВРЕМЯ 
РАБОТЫ КОТОРОГО ПОРЯДКА $\log N$. пОЭТОМУ БОЛЬШИЕ ПРИОРИТЕТНЫЕ ОЧЕРЕДИ ОБЫЧНО
ПРЕДСТАВЛЯЮТ В ВИДЕ ПИРАМИД ИЛИ ЛЕВОСТОРОННИХ ДЕРЕВЬЕВ. в П.~6.2.3 МЫ 
ОБСУДИМ ЕЩЕ ОДИН СПОСОБ ПРЕДСТАВЛЕНИЯ ЛИНЕЙНЫХ СПИСКОВ В ВИДЕ 
\emph{СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ}, КОТОРЫЙ ПРИВОДИТ К ТРЕТЬЕМУ МЕТОДУ, 
ПРИГОДНОМУ ДЛЯ ПРЕДСТАВЛЕНИЯ ПРИОРИТЕТНЫХ ОЧЕРЕДЕЙ, С ВРЕМЕНЕМ РАБОТЫ 
ПОРЯДКА $\log N$. пОЭТОМУ УМЕСТНО СРАВНИТЬ ЭТИ ТРИ МЕТОДА.

мЫ ВИДЕЛИ, ЧТО ОПЕРАЦИИ НАД ЛЕВОСТОРОННИМИ ДЕРЕВЬЯМИ В ЦЕЛОМ НЕСКОЛЬКО 
БЫСТРЕЕ, ЧЕМ ОПЕРАЦИИ НАД ПИРАМИДАМИ, НО ПИРАМИДЫ ЗАНИМАЮТ МЕНЬШЕ ПАМЯТИ. 
сБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ ЗАНИМАЮТ ПРИМЕРНО СТОЛЬКО ЖЕ ПАМЯТИ, СКОЛЬКО 
ЛЕВОСТОРОННИЕ ДЕРЕВЬЯ (БЫТЬ МОЖЕТ, ЧУТЬ МЕНЬШЕ); ОПЕРАЦИИ НАД НИМИ 
МЕДЛЕННЕЕ, ЧЕМ НАД ПИРАМИДАМИ, А ПРОГРАММИРОВАНИЕ СЛОЖНЕЕ, НО СТРУКТУРА 
СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ В НЕКОТОРЫХ ОТНОШЕНИЯХ СУЩЕСТВЕННО БОЛЕЕ ГИБКАЯ. 
рАБОТАЯ С ПИРАМИДАМИ, НЕ ТАК ПРОСТО ПРЕДСКАЗАТЬ, ЧТО ПРОИЗОЙДЕТ С 
ЭЛЕМЕНТАМИ, ЕСЛИ У НИХ РАВНЫЕ КЛЮЧИ; НЕЛЬЗЯ ГАРАНТИРОВАТЬ, ЧТО ЭЛЕМЕНТЫ С 
РАВНЫМИ КЛЮЧАМИ БУДУТ ОБРАБАТЫВАТЬСЯ ПО ПРИНЦИПУ "ПОСЛЕДНИМ 
ВКЛЮЧАЕТСЯ--- ПЕРВЫМ ИСКЛЮЧАЕТСЯ" ИЛИ "ПЕРВЫМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ 
ИСКЛЮЧАЕТСЯ", ЕСЛИ ТОЛЬКО КЛЮЧ НЕ РАСШИРЕН И НЕ СОДЕРЖИТ 
ДОПОЛНИТЕЛЬНОГО ПОЛЯ "ПОРЯДКОВЫЙ НОМЕР ВСТАВКИ", И ТОГДА РАВНЫХ КЛЮЧЕЙ 
ПРОСТО НЕТ. с ДРУГОЙ СТОРОНЫ, ЕСЛИ ПРИМЕНЯТЬ СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ, 
МОЖНО ЛЕГКО ОГОВОРИТЬ ТВЕРДЫЕ УСЛОВИЯ
ОТНОСИТЕЛЬНО РАВНЫХ КЛЮЧЕЙ. мОЖНО ТАКЖЕ ВЫПОЛНЯТЬ ТАКИЕ ДЕЙСТВИЯ, КАК 
"ВСТАВИТЬ $x$ НЕПОСРЕДСТВЕННО ПЕРЕД (ИЛИ ПОСЛЕ) $y$". сБАЛАНСИРОВАННЫЕ 
ДЕРЕВЬЯ СИММЕТРИЧНЫ, ТАК ЧТО В ЛЮБОЙ МОМЕНТ МОЖНО ИСКЛЮЧИТЬ ЛИБО 
НАИБОЛЬШИЙ, ЛИБО НАИМЕНЬШИЙ ЭЛЕМЕНТ,
В ТО ВРЕМЯ КАК ЛЕВОСТОРОННИЕ ДЕРЕВЬЯ И ПИРАМИДЫ ДОЛЖНЫ БЫТЬ
ТАК ИЛИ ИНАЧЕ ОРИЕНТИРОВАНЫ. (сМ. ТЕМ НЕ МЕНЕЕ УПР.~31, В КОТОРОМ
%% 186
\picture{рИС. 28. тАК ВЫГЛЯДИТ ПИРАМИДА...}
%%187
ПОКАЗАНО, КАК СТРОИТЬ \emph{СИММЕТРИЧНЫЕ} ПИРАМИДЫ.) 
сБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ МОЖНО ИСПОЛЬЗОВАТЬ КАК ДЛЯ ПОИСКА, ТАК И ДЛЯ 
СОРТИРОВКИ; И ИЗ СБАЛАНСИРОВАННОГО ДЕРЕВА МОЖНО ДОВОЛЬНО БЫСТРО УДАЛЯТЬ 
ПОСЛЕДОВАТЕЛЬНЫЕ БЛОКИ ЭЛЕМЕНТОВ. нО ДВА СБАЛАНСИРОВАННЫХ ДЕРЕВА НЕЛЬЗЯ 
СЛИТЬ МЕНЕЕ ЧЕМ ЗА $O(N)$ ШАГОВ, В ТО ВРЕМЯ КАК ДВА ЛЕВОСТОРОННИХ ДЕРЕВА 
МОЖНО СЛИТЬ ВСЕГО ЗА $O (\log N)$ ШАГОВ.

иТАК, ПИРАМИДЫ НАИБОЛЕЕ ЭКОНОМНЫ С ТОЧКИ ЗРЕНИЯ ПАМЯТИ;
ЛЕВОСТОРОННИЕ ДЕРЕВЬЯ ХОРОШИ ТЕМ, ЧТО МОЖНО БЫСТРО СЛИТЬ ДВЕ 
НЕПЕРЕСЕКАЮЩИЕСЯ ПРИОРИТЕТНЫЕ ОЧЕРЕДИ; И, ЕСЛИ НУЖНО, ЗА УМЕРЕННОЕ 
ВОЗНАГРАЖДЕНИЕ МОЖНО ПОЛУЧИТЬ ТУ ГИБКОСТЬ, КАКУЮ ПРЕДОСТАВЛЯЮТ 
СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ.

\section * аНАЛИЗ ПИРАМИДАЛЬНОЙ СОРТИРОВКИ. аЛГОРИТМ H ДО СИХ ПОР НЕ БЫЛ 
ПОЛНОСТЬЮ ПРОАНАЛИЗИРОВАН, НО НЕКОТОРЫЕ ЕГО СВОЙСТВА МОЖНО ВЫВЕСТИ БЕЗ 
ОСОБОГО ТРУДА. пОЭТОМУ МЫ ЗАВЕРШИМ ЭТОТ ПУНКТ ДОВОЛЬНО ПОДРОБНЫМ 
ИССЛЕДОВАНИЕМ, КАСАЮЩИМСЯ ПИРАМИД.

нА РИС. 28 ПОКАЗАНА ФОРМА ПИРАМИДЫ ИЗ 26 ЭЛЕМЕНТОВ;
КАЖДЫЙ УЗЕЛ ПОМЕЧЕН ДВОИЧНЫМ ЧИСЛОМ, СООТВЕТСТВУЮЩИМ ЕГО ИНДЕКСУ В 
ПИРАМИДЕ. зВЕЗДОЧКАМИ В ЭТОЙ ДИАГРАММЕ ПОМЕЧЕНЫ
ТАК НАЗЫВАЕМЫЕ \dfn{ОСОБЫЕ УЗЛЫ}, КОТОРЫЕ ЛЕЖАТ НА ПУТИ ОТ~1 К~$N$.

оДНА ИЗ НАИБОЛЕЕ ВАЖНЫХ ХАРАКТЕРИСТИК ПИРАМИДЫ---НАБОР РАЗМЕРОВ ЕЕ 
ПОДДЕРЕВЬЕВ. нАПРИМЕР, НА РИС.~28 РАЗМЕРЫ ПОДДЕРЕВЬЕВ С КОРНЯМИ В УЗЛАХ 
1,2, \dots, 26 РАВНЫ СООТВЕТСТВЕННО
$$
26^*, 15,10^*, 7, 7, 6^*, 3, 3, 3, 3, 3, 3, 2^*, 1,1,1,1,1,1,1,1,1,1,1,1, 1^*.
\eqno (12)
$$
зВЕЗДОЧКАМИ ОТМЕЧЕНЫ \dfn{ОСОБЫЕ ПОДДЕРЕВЬЯ} С КОРНЯМИ В ОСОБЫХ УЗЛАХ; В 
УПР.~20 ПОКАЗАНО, ЧТО ЕСЛИ $N$ ИМЕЕТ ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ
$$
N=(b_n b_{n-1} \ldots b_1 b_0)_2, \qquad n=\lfloor\log_2 N\rfloor,
\eqno (13)
$$
ТО РАЗМЕРЫ ОСОБЫХ ПОДДЕРЕВЬЕВ РАВНЫ
$$
(1 b_{n-1}\ldots b_1 b_0)_2, (1 b_{n-2}\ldots b_1 b_0)_2, \ldots,
(1 b_1 b_0)_2, (1 b_0)_2, (1)_2.
\eqno(14)
$$
(нЕОСОБЫЕ ПОДДЕРЕВЬЯ ВСЕГДА АБСОЛЮТНО СБАЛАНСИРОВАНЫ, ТАК ЧТО ИХ РАЗМЕРЫ 
ВСЕГДА ИМЕЮТ ВИД $2^k-1$. в УПР.~21 ПОКАЗАНО, ЧТО СРЕДИ НЕОСОБЫХ 
ПОДДЕРЕВЬЕВ ИМЕЕТСЯ РОВНО
$$
\matrix{
\hbox{$\lfloor(N-1)/2 \rfloor$ РАЗМЕРА  1,} &  & 
\hbox{$\lfloor(N-2)/4\rfloor$ РАЗМЕРА 3,}\hfill\cr
\hbox{$\lfloor(N-4)/8\rfloor$ РАЗМЕРА 7,} & \ldots  & 
\hbox{$\lfloor(N-2^{n-1})/2^n\rfloor$ РАЗМЕРА $(2^n-1)$,}\hfill\cr
}
\eqno(15)
$$
нАПРИМЕР, НА РИС.~28 ИЗОБРАЖЕНО ДВЕНАДЦАТЬ НЕОСОБЫХ ПОДДЕРЕВЬЕВ 
РАЗМЕРА~1, ШЕСТЬ ПОДДЕРЕВЬЕВ РАЗМЕРА~3, 
ДВА---РАЗМЕРА~7 И ОДНО---РАЗМЕРА~15.
%%188

\bye