» 0.19677V+(-1)0.3;

к 0.744037V - 1.3 in TV; CJV a 0.470347V - 0.8 In TV;

Dn « (1.8 ± 0.2)[TV четное].

Нетрудно определить также максимальные и минимальные значения. Для построения пирамиды требуется всего 0{N) шагов (см. упр. 23).

Этим, по существу, завершается анализ фазы построения пирамиды в алгоритме Н. Анализ фазы выбора - совсем другая задача, которая еще ожидает своего решения! Пусть пирамидальная сортировка применяется к N элементам; обозначим через А, В, Cjy и D средние значения величин Л, В, С и Г> во время фазы выбора. Поведение алгоритма Н подвержено сравнительно малым колебаниям около эмпирически установленных средних значений

» 0.1527V;

CilNlgN -IAIN;

Dj!,KlgN±2.

Тем не менее до сих пор не найдено адекватного теоретического объяснения поведения Dj!j или эмпирически подобранных значений констант 0.152, 2.61 и 1.41. Ведущие члены в выражениях для Bpf и Cjy, однако, очень изящно обоснованы Р. Шаффером и Р. Седгевиком (см. упр. 30). Шаффер также доказал, что минимальное и максимальное значения CJv равны iVlgiV и 7Vlg7V соответственно.

УПРАЖНЕНИЯ

1. [10] Является ли сортировка посредством простого выбора (алгоритм S) устойчивой?

2. [15] Почему в алгоритме S более удобно находить сначала наибольший элемент, затем - наибольший из оставшихся и т. д., вместо того чтобы находить сначала наименьший элемент, затем - наименьший из оставшихся и т. д.?

3. [М21] (а) Докажите, что если алгоритм S применяется к случайной перестановке множества {1, 2,..., Л}, то в результате первого выполнения шагов S2 и S3 получается случайная перестановка множества {1,2,..., Л-1}, за которой следует Л. (Иначе говоря, массив Ki...Kn-i с одинаковой вероятностью может быть любой перестановкой множества {1, 2,... ,Л-1}.) (Ь) Следовательно, если через Bn обозначить среднее значение величины В в программе S, то при условии, что исходный массив упорядочен случайным образом, имеем Bn = Hn - 1 + Bn-i- [Указание. См. выражение 1.2.10-(16).]

► 4. [М25] На шаге S3 алгоритма S ничего не происходит, если г = j. Не лучше ли перед выполнением шага S3 проверить условие г = j? Чему равно среднее число случаев выполнения условия i = j на шаге S3, если исходный массив случаен?

5. [20] Чему равно значение параметра В в анализе программы S для исходного массива ЛГ...3 21?

6. [М29] (а) Пусть aia2...aN - перестановка множества {1,2, ...,Л} с С циклами, / инверсиями и такая, что при ее сортировке с помощью программы S выполняется В обменов на правосторонний максимум. Докажите, что 2J5 < I + N - С. [Указание. См. упр. 5.2.2-1.] (Ь) Покажите, что I + N - С < [N/2\; следовательно, В не превышает [N/ij.

7. [Af.i] Найдите дисперсию параметра В в программе S как функцию от Л, считая, что исходный массив случаен.

► 8. [2i\ Покажите, что если при поиске max (ATiATj) на шаге S2 просматривать ключи слева направо (Ki, К2, ..., Kj), а не наоборот, как в программе S, то можно сократить число сравнений при следующих итерациях шага S2. Напишите MIX-программу, реализующую этот подход.

9. [М25] Чему равно среднее число сравнений, выполняемых алгоритмом из упр. 8 для случайного исходного массива?

10. [12] Как будет выглядеть дерево, изображенное на рис. 23, после вывода 14 из 16 первоначальных элементов?

11. [10] Как будет выглядеть дерево, изображенное на рис. 24, после вывода элемента 908?

12. [М20] Сколько раз будет выполнено сравнение -оо с -оо, если применить восходящий метод, представленный на рис. 23, для упорядочения массива из 2" элементов?

13. [20] (Дж. У. Дж. Уильяме (J. W. J. Williams).) На шаге Н4 алгоритма Н различаются три случая: j < г, j = г и j > г. Покажите, что если К > Kr+i, то можно так упростить шаг Н4, что разветвление будет происходить лишь по двум ветвям. Как следует изменить шаг Н2, чтобы обеспечить в процессе пирамидальной сортировки выполнение условия К >

Кг + 1?

14. [10] Покажите, что простая очередь - частный случай приоритетной. (Объясните, какие ключи нужно присваивать элементам, чтобы процедура "наибольший из включенных первым исключается" была эквивалентна процедуре "первым пришел - первым вышел" ?) Является ли стек также частным случаем приоритетной очереди?

► 15. [М22] (Б. Э. Чартрс (В. А. Chartres).) Придумайте быстрый алгоритм построения таблицы простых чисел < n, в котором используется приоритетная очередь, чтобы избежать операций деления. [Указание. Пусть наименьший ключ в приоритетной очереди будет наименьшим нечетным непростым числом, большим, чем самое последнее нечетное число, рассматриваемое как кандидат в простые числа. Попытайтесь свести к минимуму количество элементов в этой очереди.]

16. [20] Постройте эффективный алгоритм, который позволяет вставить новый ключ в данную пирамиду из п элементов, порождая пирамиду из п Ч-1 элементов.

17. [20] Алгоритм из упр. 16 можно использовать для построения пирамиды вместо метода "уменьшать I до 1", применяемого в алгоритме Н. Порождают ли оба метода из одного и того же исходного массива одну и ту же пирамиду?

► 18. [21] (Р. У. Флойд (R. W. Floyd).) Во время фазы выбора в алгоритме пирамидальной сортировки ключ К, как правило, принимает довольно малые значения, и поэтому почти при всех сравнениях на шаге Н6 обнаруживается, что К < Kj. Как можно изменить алгоритм, чтобы клМ К не сравнивался с Kj в основном цикле вычислений, и таким образом почти напо. h .пину уменьшить число сравнений?

19. [21] Предложите алгоритм исключения данного элемента из пирамиды размером Л, порождающий пирамиду размером n - 1.

20. [М20] Покажите, что формулы (14) задают размеры особых поддеревьев пирамиды.

21. [М24] Докажите, что формулы (15) задают размеры неособых поддеревьев пирамиды.

► 22. [20] Какие перестановки множества {1,2,3,4,5} на фазе построения пирамиды в алгоритме Н преобразуются в 5 3 412?

23. [M2(S] (а) Докажите, что длина пути В в алгоритме протаскивания никогда не превышает [lg(r/Z)J. (b) Согласно неравенствам (8) ни при каком конкретном применении

алгоритма Н величина В не может превзойти A[lgAJ. Найдите максимальное значение В по всевозможным исходным массивам как функцию от Л. (Нужно доказать, что существует такой исходный массив, на котором В принимает это максимальное значение.)

24. [М24] Выведите точную формулу стандартного отклонения величины JSjv (суммарная длина пути, пройденного по дереву во время фазы построения пирамиды в алгоритме Н).

25. [М20] Чему равен средний вклад в значение параметра С за время первой операции протаскивания, когда I = 1 и г = N, если = 2" - 1?

26. [МЗО] Выполните упр. 25: (а) для = 26, (Ь) для произвольного Л.

27. [М25] (Т. Клаузен (Т. Clausen), 1828.) Докажите, что

(Положив x = , получите очень быстро сходящийся ряд для вычисления (19).)

28. [35] Продумайте идею тернарных пирамид, основанных на полных тернарных, а не бинарных деревьях. Будет ли тернарная пирамидальная сортировка выполняться быстрее бинарной?

29. [26] (У. С. Браун (W. S. Brown).) Постройте алгоритм умножения многочленов или степенных рядов (aix + агх + ){bix + b2X- + )> который порождал бы коэффициенты произведения cia;"*"-" + в том порядке, в котором перемножаются коэффициенты исходных многочленов. [Указание. Воспользуйтесь подходящей приоритетной очередью.]

► 30. [HMS5] (Р. Шаффер (R. Schaffer) и Р. Седгевик (R, Sedgewick).) Пусть hnm - число пирамид элементов {1,2,..., п}, для которых фаза выбора даст ровно т продвижений. Докажите, что

hnrn<2"Yllgk,

к =2

И используйте это соотношение для того, чтобы показать, что среднее число продвижений, выполняемых алгоритмом Н, равно NlgN + 0{NloglogN).

31. [37] (Дж. У. Дж. Уильяме.) Покажите, что если две пирамиды подходящим образом совместить "основание к основанию", то появится возможность поддерживать структуру, в которой в любой момент можно за 0(log п) шагов исключить либо наибольший, либо наименьший элемент. (Такую структуру можно назвать приоритетным деком.)

32. [М28] Докажите, что число продвижений В при пирамидальной сортировке всегда оказывается не меньше -NlgN-I-O(N), если все сортируемые ключи различны. Указание. Рассмотрите продвижение [N/2] наибольших ключей.

33. [21] Разработайте алгоритм слияния двух непересекающихся приоритетных очередей, представленных в виде левосторонних деревьев, в одну. (В частности, если одна из данных очередей содержит всего один элемент, то ваш алгоритм будет вставлять его в другую очередь.)

34. [Mi] Сколько можно построить левосторонних деревьев из узлов, если игнорировать значения поля KEY? Эта последовательность начинается с чисел 1, 1, 2, 4, 8, 17, 38, 87, 203, 482, 1160, ...; покажите, что данное число асимптотически стремится к abN~ при соответствующим образом выбранных константах а и 6, используя методику, аналогичную примененной в упр. 2.3.4.4-4.