12 18,

/ \ / \

44 12 18 67

/\/\ /\/\

44 Б5 12 42 94 18 q 67

Рис 2.5. Заполнение дыр .

Разумеется, было бы весьма желательно избавиться от необходимости в дырах (-оо), которые в конце заполняют все дерево и приводят к большому количеству ненужных сравнений. Кроме того, нужно найти способ представить дерево из . элементов в п единицах памяти вместо 2п-1 единиц, как показано выше. Это действительно можно сделать с помощью метода, который его изобретатель Дж. Уильяме [2.14] назвал пирамидальной сортировкой. Ясно, что этот метод дает существенное улучшение по сравнению с более привычными способами сортировки по дереву.

Пирамида определяется как последовательность ключей

ifaKafl, что

1Ля всякого 1 = /, .... г/2. Если двоичное дерево представ-*ено в виде массива, как показано на рис. 2.6, то, следова-льно, деревья сортировки на рис. 2.7 и 2.8 являются пира- рядами, и, в частности, элемент hi пирамиды является ее Шеньшим элементом

1 Л, = min (Л,... Л„).

Ьерь предположим, что дана пирамида с элементами ., h, для некоторых значений / и г и нужно добавить

по сравнению с простым методом, требующим шагов по сравнению с сортировкой Шелла, которая требует > шагов.

Конечно, при сортировке с помощью дерева задача хране-ддформации стала сложнее и поэтому увеличилась слож-я* отдельных шагов; в конечном счете для хранения воз- jjjgro объема информации, получаемой на начальном про- Р° - (j.y.jKHO строить некую древовидную структуру. Наша черёдная задача - найти способы эффективной организации этой информации.

новый пирамиду

элемент х для того, чтобы сформировать расширен 1ду ht, hr. Возьмем, например, исходную пирац^*; hi,..., hj, показанную на рис. 2.7, и расширим эту пиращ^ влево , добавив элемент hi = 44. Новый элемент х снача? помещается в вершину дерева, а затем просеивается пути, на котором на.ходятся меньшие по сравнению с элементы, которые одновременно поднимаются вверх; так^

/\-/\--/\ /\

12 tl,4 IE

Рис. 2.6. Массив h, расположенный в виде бинарного дерева.

Б5 4 18 12

Рис. 2.7. Пирамида из семи э-пементов.

Б5 94 18

Рис. 2.8. Просеивание ключа 44 через пирамиду.

образом формируется новая пирамида. В данном пример значение 44 сначала меняется местами с 06, затем с 12, и та формируется дерево, показанное на рис. 2.8. Далее мы пР цесс просеивания будем формулировать следующим образ i, j - пара индексов, обозначающих элементы, которЬ

нужно менять местами на каждом шаге просеивания, предоставляем читателю возможность самому убедиться,

Предложенный способ просеивания действительно позвоЛ сохранить условия (2.13), определяющие пирамиду.

Изяш,ный способ построения пирамиды in situ был пР ложен Р. У. Флойдом. В нем используется следующая Dp

па просеивания (программа 2.7). Дан массив fti, .... h ; что элементы hn/z+i ... hn уже образуют пирамиду, по-льку не существует двух индексов i, /, ; := 9;

( лй /= 2/-}-1). Эти элементы составляй

таких, что I - 2i . , составляют последователь-

которую можно рассматривать как нижний ряд соот- ёующего двоичного дерева (см. рис. 2.6), где не тре-

..itoeeiutt siftihr: index);

label 13; var index; x: item; begin I := /; 7 := 2*/; x := d[ih

while J r йо , begin UJ < r then

if аЦ] .key > .fcey then J

if л: .key [jfl .fce; then goto 13; oM := aU]; i := /j / == 2. {sift}

end; 13: a[jj := л; end

Программа 2.7. Просеивание.

буется никакого упорядочения. Теперь пирамида расширяется влево: на каждом шаге добавляется новый элемент и при помощи просеивания помещается на соответствующее место.

Таблица 2.6. Построение пирамиды

Этот процесс иллюстрируется табл. 2.6 и приводит к пирамиде, показанной на рис. 2.6. Следовательно, процесс подстроения пирамиды из п элементов in situ можно описать едующим образом:

/ := (и div 2) + i; whUe / > 1 do

begin / := siftQ)