35. [26] Если в левостороннее дерево добавить связи UP (ср. с анализом деревьев с тремя связями в разделе 6.2.3), то получим возможность исключать из приоритетной очереди произвольный узел Р следующим образом: слить LEFT(P) и RIGHT (?) и поместить полученное поддерево на место Р, затем исправлять поля DIST предков узла Р до тех пор, пока не будет достигнут либо корень, либо узел, поле DIST которого не меняется.

Докажите, что при этом никогда не потребуется изменить более чем 0(log ) полей DIST, несмотря даже на то, что дерево может содержать очень длинные восходящие пути.

36. [18] {Замещение наиболее давно использованной страницы.) Во многих операционных системах используется алгоритм следующего типа: над набором узлов допустимы две onepaiyin: (i) использование узла и (ii) замещение наиболее давно использованного узла новым. Какая структура данных облегчает нахождение наиболее давно использованного узла?

37. [НМ32] Пусть ел? (А:) - предполагаемое расстояние между самым большим к-м элементом и корнем в случайной пирамиде из элементов и пусть е(А:) = lim?-+oo е;у(А:). Тогда е(1) = О, е(2) = 1, е(3) = 1.5, а е(4) = 1.875. Найдите значениеасимптотического выражения для е{к) через 0{к~).

38. [М21] Найдите простое рекуррентное соотношение для мультимножества Miv размеров поддеревьев в пирамиде или в полном бинарном дереве, имеющем внутренних узлов.

5.2.4. Сортировка методом слияния

Слияние* означает объединение двух или более упорядоченных массивов в один упорядоченный массив. Можно, например, слить подмассивы 503 703 765 и 087 512 677 и получить 087 503 512 677 703 765. Простой способ сделать это - сравнить два наименьших элемента, вывести наименьший из них и повторить эту процедуру. Начав с

получим

затем

087 503 512

и т. д. Необходимо решить, что делать в случае, когда исчерпается один из массивов. Весь процесс подробно описан в следующем алгоритме.

Алгоритм М {Двухпутевое слияние). Этот алгоритм осуществляет слияние упорядоченных массивов a;i < < • • • < и у1 < у2 < • • • < Уп в массив .zi < Z2 < • • • <

Zm+n (рис. 29).

Ml. [Начальная установка.] Установить г-f- 1, j-f- 1, к 1.

* В англоязычной литературе термину слияние соответствуют два равнозначных термина - merging и collating. - Прим. перев.

Ml. Начальная установка

М2. Найти

наименьший элемент

МЗ. Вывести Xi

Массив X исчерпан

М4. Передать yj, - ,Уп

М5. Вывести ?/j

Массив у исчерпан

Мб. Передать Xi,...,Xm

Рис. 29. Слияние xi < • • • < Хт с j/i < < j/„.

М2. [Найти наименьший элемент.] Если Х{ < yj, перейти к шагу МЗ; в противном случае перейти к шагу М5.

МЗ. [Вывести Х{.] Установить Zk <- xi, к <- к + 1, i <- i + 1. Если г < тп, вернуться к шагу М2.

М4. [Передать у,...,у„.] Установить [zk,. . ,Zm+n) {yj,---,yn) и завершить выполнение алгоритма.

М5. [Вывести yj.] Установить Zk yj, к <г- к + \, j <г- j + 1. Если j <п, вернуться к шагу М2.

Мб. [Передать xi,... ,Хт-] Установить {zk,. ,Zm+n) {xi, .,Хт) и завершить выполнение алгоритма.

В разделе 5.3.2 будет показано, что эта простая процедура, по существу, - наилучший из возможных способов слияния на компьютере с обычной архитектурой, когда тип. (Но, если тп гораздо меньше п, можно разработать более эффективные алгоритмы сортировки, хотя в общем случае они довольно сложны.) Алгоритм М без существенной потери эффективности можно немного упростить, добавив в конец исходных массивов искусственных "стражей" (ограничивающие элементы x,n+i = Уп+1 = оо) И остановившись перед выводом оо. Анализ алгоритма М приведен в упр. 2.

Общий объем операций, выполняемых алгоритмом М, по существу, пропорционален m -f- п, откуда понятно, почему считается, что слияние - более простая задача, чем сортировка. Однако задачу сортировки можно свести к слияниям, сливая все более длинные подмассивы до тех пор, пока не будет рассортирован весь массив. Такой подход можно рассматривать как развитие идеи сортировки методом вставок: вставка нового элемента в упорядоченный массив - частный случай слияния при п = 1. Чтобы ускорить процесс вставок, можно рассмотреть вставку нескольких элементов за один раз, группируя несколько операций, а это естественным образом приведет к общей идее сортировки методом слияния. С исторической точки зрения метод слияний - один из самых первых методов сортировки при помощи компьютеров; он был предложен Джоном фон Нейманом (John von Neumann) еще в 1945 году (см. раздел 5.5).

Довольно подробно слияние рассматривается в разделе 5.4 в связи с алгоритмами внешней сортировки, а в настоящем разделе речь пойдет о сортировке в оперативной памяти с произвольным доступом.

В табл. 1 проиллюстрирована сортировка методом слияния, когда "свечка сжигается с обоих концов", подобно тем процедурам просмотра элементов массива, которые применялись при быстрой сортировке, поразрядной обменной сортировке и т. д. Будем анализировать исходный массив слева и справа, двигаясь к середине. Пропустим пока первую строку и рассмотрим переход от второй строки к третьей. Слева мы видим восходяшую серию 503 703 765, а справа, если читать справа налево, имеем серию 087 512 677. Слияние этих двух последовательностей дает подмассив 087 503 512 677 703 765, который помещается слева в строке 3. Затем ключи 061 612 908 в строке 2 сливаются с 170 509 897 и результат (061 170 509 612 897 908) записывается справа в строке 3. Наконец, 154 275 426 653 сливается с 653 (перекрытие обнаруживается прежде, чем оно может привести к нежелатель"ным последствиям) и результат записывается слева. Точно так же строка 2 получается из строки 1 исходного массива.

Таблица 1

СОРТИРОВК.\ МЕТОДОМ ЕСТЕСТВЕННОГО ДВУХПУТЕВОГО СЛИЯНИЯ

503 087 512 061 908 170 897 275 Гб53 426 154 509 612 677 765 703

503 703 765 061 612 908 154 275 426 653 897 509 170 677 512 087

087 503 512 677 703 765 154 275 426 653 908 897 612 509 170 061

061 087 170 503 509 512 612 677 703 765 897 908 653 426 275 154

061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908

Вертикальными линиями в табл. 1 отмечены границы между сериями. Это так называемые ступеньки вниз, где меньший элемент следует за большим. В общем случае в середину массива возникает двусмысленная ситуация, когда при движении с обоих концов считывается один и тот же ключ; это не приведет к осложнениям, если проявить чуточку осторожности, как в следующем алгоритме. Такой метод по традиции Нс1зывается "естественным" слиянием, потому что в нем используются серии, которые "естественно" образуются в исходном массиве.

Алгоритм N {Сортировка методом естественного двухпутевого слияния). При сортировке записей i?i,..., Rn используются две области памяти, в каждой из которых может содержаться N записей. Для удобства обозначим записи, находящиеся во второй области, через Rn+i , R2N, хотя в действительности запись Rn+i может и не примыкать непосредственно к Rn- Начальное содержимое записей Rn+i , , R2N не имеет значения. После завершения сортировки ключи будут упорядочены таким образом: iTi < • • • < Kn (рис. 30).

N1. [Начальная установка.] Установить s <- 0. (При s = О будем пересылать записи из области {Ri,...,Rn) в область {Rn+iR2N), при s = 1 области по отношению к пересылкам поменяются ролями.)