Рис. 20.4 Биномиальное дерево В4 с вершинами, пронумерованными в порядке «левое поддерево, . . . , правое поддерево, вершина»; номера записаны в двоичной системе.

Доступ к биномиальной куче Н осуществляется с помощью поля head[H] - указателя на первый корень в корневом списке кучи Н. Если куча Н пуста, то head[H] = nil.

Упражнения

20.1-1 Пусть х - вершина одного из биномиальных деревьев в биномиальной куче, причём sibling[x] ф nil. Как соотносятся значения degree[sibling[x]] и degree[x]? (Ответ зависит от того, является ли х корнем.)

20.1-2 Пусть х - некорневая вершина биномиального дерева. Сравнить degree[p[x]] и degree[x].

20.1-3 Расположим вершины биномиального дерева Bj~ в таком порядке, чтобы каждая вершина следовала за своими потомками. При этом сначала идут потомки её левого ребёнка, затем сам этот ребенок, затем потомки следующего ребенка, он сам и т. д. (postorder walk). Пронумеруем вершины, записав номера в двоичной системе счисления (рис. 20.4). Покажите, что глубина вершины определяется числом единиц (корень имеет одни единицы, его дети на одну единицу меньше и т.д.), а степень вершины равняется числу единиц у правого края двоичной записи. Сколько имеется двоичных строк длины к, содержащих ровно j единиц, и где находятся соответствующие им вершины?

20.2. Операции с биномиальными кучами

В этом разделе приведены реализации операций с биномиальными кучами. Время работы этих операций указано в таблице 20.1. Мы докажем только верхние оценки, оставляя нижние в качестве упр. 20.2-10.

Создание новой кучи

Процедура Make-Binomial-Heap создаёт и возвращает объект Н, для которого head[H] = nil (время работы 0(1)).

Поиск минимального ключа

Процедура Binomial-Heap-Minimum возвращает указатель на вершину с минимальным ключом в биномиальной куче Я, состоящей из га вершин. Мы используем специальное значение оо, которое больше всех значений ключей (см. упр. 20.2-5).

Binomial-Heap-Minimum (Я)

1у <- nil

2ж <- head[H]

3min <- оо

4while х ф nil

5do if key[x] < min

6then min <- key[x]

7у <- x

8ж <- вШгшж]

9return у

В биномиальных деревьях наименьшие элементы стоят в корнях, так что достаточно выбрать минимальный элемент корневого списка. Процедура Binomial-Heap-Minimum просматривает этот список, храня в переменной min минимальное из просмотренных значений, а в переменной у - вершину, где оно достигается.

Например, для кучи рис. 20.3 процедура Binomial-Heap-Minimum возвращает указатель на вершину с ключом 1.

Длина корневого списка не превосходит [lg raj +1, поэтому время работы процедуры Binomial-Heap-Minimum есть О (lgra).

20.2.1. Объединение двух куч

Операция Binomial-Heap-Union, соединяющая две биномиальные кучи в одну, используется в качестве подпрограммы большинством остальных операций.

[Идея проста: пусть есть две биномиальные кучи с т и га элементами. Размеры деревьев в них соответствуют слагаемым в разложениях чисел т и га в сумму степеней двойки. При сложении столбиком в двоичной системе происходят переносы, которые соответствуют слияниям двух биномиальных деревьев Bk-i в дерево Bj~. Надо только посмотреть, в каком из сливаемых деревьев корень меньше, и считать его верхним.]

Опишем операцию объединения подробно. Начнём со вспомогательной операции Binomial-Link, которая соединяет два биномиальных дерева одного размера (Bk-i), корнями которых являются вершины у и z, делая вершину z родителем вершины у и корнем дерева Bj~.

Binomial-Link (у, z)

1р[у] <г- z

2sibling[y] <- child[z]

3child[z] <- у

4degree[z] <- degree[z] + 1

Время работы этой процедуры - 0(1) (удачным образом оказывается, что вершину у надо добавить в начало списка детей вершины z, что легко сделать в представлении «левый ребёнок, правый сосед»).

Теперь напишем процедуру Binomial-Heap-Union, которая объединяет биномиальные кучи Н\ и Н2 (сами кучи при этом исчезают). Помимо процедуры Binomial-Link, нам понадобится процедура Binomial-Heap-Merge, которая сливает корневые списки куч Н\ и Н2 в единый список, вершины в котором идут в порядке возрастания степеней. (Эта процедура аналогична процедуре Merge из раздела 1.3.1, и её мы оставляем читателю в качестве упр. 20.2-2.)

Binomial-Heap-Union(#i, Н2)

1Я <- Make-Binomial-Heap()

2head[H] <- Binomial-Heap-Merge(#i, Н2)

3освободить память, занятую под Н\ и Н2

(сохранив списки, на которые указывают Н\ и Н2)

4if head[H] = nil

5then return H

6prev-x <- NIL

7x <- head[H]

8next-x <- sibling[x]

9while next-x ф NIL

10do if (degree[x] ф degree[next-x]) or

(sibling[next-x\ ф NIL

and degree[sibling[next-x]] = degree[x])

11then prev-x <- x> Случаи 1 и 2

12x <- next-x> Случаи 1 и 2

13else if &еу[ж] key[next-x]

14then вШгшж] <- sibling[next-x] > Случай 3

15BlNOMlAL-LlNK(nea;4-a;, ж) > Случай 3

16else if prev-x = NIL> Случай 4

17then /iea<i[if] <- next-x > Случай 4

18else sibling[prev-x] <- next-x\> Случай 4

19Binomial-Link, next-x) > Случай 4

20ж <- next-x> Случай 4

21next-x <- вШгшж]

22 return H