• ослабленные пирамиды [J. R. Driscoll, Н. N. Gabow, R. Shrairman, R. E. Tarjan, CACM 31 (1988), 1343-1354];

• острога [M. J. Fischer, M. S. Paterson, JACM 41 (1994), 3-30];

• "горячие" очереди [В. V. Cherkassky, A. V. Goldberg, C. Silverstein, SODA 8 (1997), 83-92].

He все из этих методов выдержали испытание временем. Левосторонние деревья сегодня - уже анахронизм; они используются разве что в тех приложениях, в которых необходимо жестко соблюдать дисциплину "последним пришел - первым вышел" Детали реализации биномиальных очередей и пирамид Фибоначчи можно найти в работе D. Е. Knuth, The Stanford GraphBase (New York: ACM Press, 1994), 475-489.

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

На рис. 28 показана форма пирамиды из 26 элементов; каждый узел помечен двоичным число.м, соответствующим его индексу в пирамиде. Звездочками на этой диаграмме помечены так называемые особые узлы, которые лежат на пути от 1 к iV.

Одна из наиболее важных характеристик пирамиды - множество размеров ее поддеревьев. Например, на рис. 28 размеры поддеревьев с корнями в узлах 1,2,..., 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*. (12)

Звездочками помечены особые поддеревья с корнями в особых узлах; в упр. 20 показано, что если N имеет двоичное представление

iV=(6„6„ i... 6160)2, n=[lgiVJ, (13)

то размеры особых поддеревьев равны

(16„ 1 . . . 6160)2, (16„-2 . . . 6160)2, . . . , (16160)2, (160)2, (1)2. (14)

Неособые поддеревья всегда гьбсолютно сбалансированы, так что их размеры имеют вид 2* - 1. В упр. 21 показано, что среди неособых поддеревьев существует ровно

размером 1,

4 J N - 2"-1 2"

размером 3,

размером 7,

(2" - 1) размера. (15)

Например, на рис. 28 изображено двенадцать неособых поддеревьев размером 1, шесть поддеревьев размером 3, два - размером 7 и одно - размером 15.

Пусть si - размер поддерева с корнем I, а М - мультимножество {si, «2, • • •, Sn} всех этих размеров. Используя (14) и (15), легко вычислить Mn при любом заданном N. В упр. 5.1.4-20 показано, что общее число способов построения пирамиды из целых чисел {1,2,..., N} равно

m/siS2...sn=N\/]l{s\seMN}. (16)

(Tooo) QooT) (ТоТо) Гюп") (noo) (TioT)*

/1 TV 71 К TV г

(Tm)

(1оооо)(1оооГ)(10010)(1оо1 Г)(101оо)(Го1оГ)(101 iq)(Toi i i)(riooS)(i iooi)(i loid) •

Рис. 28. Так выглядит пирамида из 26 = (11010)2 элементов.

Например, количество способов такого расположения 26 букв {А, В,С,..., Z} на рис. 28, чтобы по вертикали сохранялся алфавитный порядок, составляет

26!/(2610•6•2•l•12•3•7•15).

Теперь можно проанализировать фазу построения пирамиды в алгоритме Н, т. е. вычислительные операции, которые завершаются до того, как на шаге Н2 впервые выполнится условие 1 = 1. К счастью, благодаря сформулированной ниже теореме анализ построения пирамиды можно свести к изучению независимых операций "протаскивания"

Теорема Н. Если исходными данными для алгоритма Н служит случайная перестановка множества {1,2,...,iV}, то в фазе построения пирамиды с одинаковой вероятностью может получиться любая из N\/ П I * возможных пирамид. Более того, все [N/2} операций протаскивания, выполненных в течение этой фазы, равномерны в том смысле, что по достижении шага Н8 все si возможных значений переменной i равновероятны.

Доказательство. Применим метод, который в численном анализе называется методом обратной задачи. Пусть в качестве одного из возможных результатов выполнения протаскивания задана пирамида Ki... Kn с корнем в узле I. Тогда ясно, что имеется точно si исходных конфигураций К[... iify массива, которые после протаскивания дают такой результат. Все эти исходные конфигурации имеют различные значения следовательно, рассуждая наоборот, можно получить ровно s( si+i.. .sn исходных перестановок множества {1,2,..., N), которые после завершения протаскивания в позицию / дают конфигурацию К\... Kn-

Случай, когда / = 1, типичен: пусть Ki... Kn - пирамида и пусть К[... К - массив, который преобразуется в Ki... в результате протаскивания при / = 1, К = К[. Если К = Ki, то должны иметь место равенства К = i<Lt/2j, [i/2\ ~ Kyiji и т. д. При этом Kj = Kj для всех j, не лежащих на пути от 1 к г. Обратно, при любом i в результате подобного построения получается массив К[... К, такой, что (а) операция протаскивания приводит к преобразованию массива К[... К в Ki...Kn, и (Ь) Кул2\ > Kj при 2 < [J/2J < j < N. Следовательно, возможно ровно N таких массивов К[... JFsT и операция протаскивания имеет равномерное распределение. (Пример доказательства этой теоремы приводится в упр. 22.)

Обратившись к параметрам А, В, С, D в анализе программы Н, можно видеть, что равномерная операция протаскивания, выполняемая по отношению к поддереву размером s, дает вклад [s/2}/s в среднее значение величины А. Ее вклад в среднее значение величины В равен

-{0+l + l + 2 + ---+llgs}) = -i2lgk} = -{{s+ l)[lgsj - + 2)

(см. упр. 1.2.4-42), и она дает вклад либо 2/s, либо О в среднее значение параметра/? в зависимости от того, каким является s: четным или нечетным. Несколько сложнее определить соответствующий вклад в среднее значение параметра С, так что эту задачу мы предлагаем читателю решить самостоятельно (см. упр. 26). Производя суммирование по всем операциям протаскивания, находим, что среднее значение параметра А за время построения пирамиды равно

AN = {[s/2\/s\seMN}. (17)

Аналогичные формулы имеют место и для В, С и D, так что можно без особого труда точно вычислить эти средние значения. В следующей таблице приведены типичные результаты.

Что касается асимптотики, то в Mn можно не обращать внимания на размеры особых поддеревьев, и тогда мы найдем, например, что

An = j-Y + J-l + J- + --- + OibgN)={l-la)N + 0{logN), (18)

а = е feZI = 1-60669 515241529176378 33015 23190 92458 04805-. (19)

к>1

(Это значение получил Дж. У. Ренч (мл.) (J. W. Wrench, Jr.), пользуясь преобразованием ряда из упр. 27. Пол Эрдеш (Paul Erdos) доказал, что а является иррациональным числом [J. Indian Math. Soc. 12 (1948), 63-66], а Питер Борвейн (Peter Borwein) продемонстрировал иррациональный характер многих других констант [Ргос. СатЬ. Phil. Soc. 112 (1992), 141-146].) При больших N можно использовать приближенные формулы