\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