Биномиальные пирамиды Лекция 13. Структуры данных, известные под названием сливаемых пирамид (mergeable heaps), которые поддерживают следующие семь операций. - презентация

1 Биномиальные пирамиды Лекция 13

2 Структуры данных, известные под названием сливаемых пирамид (mergeable heaps), которые поддерживают следующие семь операций. М АКЕ _Н ЕАР () создает и возвращает новую пустую пирамиду. lNSERT(H, х) вставляет узел х (с заполненным полем key) в пирамиду Н. M INIMUM (H) возвращает указатель на узел в пирамиде Н, обладающий минимальным ключом. E XTRACT _M IN (H) удаляет из пирамиды Н узел, ключ которого минимален, возвращая при этом указатель на этот узел. Union(H 1, H 2 ) создает (и возвращает) новую пирамиду, которая содержит все узлы пирамид H 1 и H 2. Исходные пирамиды при выполнении этой операции уничтожаются. D ECREASE _K EY (H, X, к) присваивает узлу х в пирамиде Н новое значение ключа к. DELETE(H, х) удаляет узел х из пирамиды Н.

3 Время выполнения операций у разных реализаций пирамид Процедура Бинарная пирамида (наихудший случай) Биномиальная пирамида (наихудший случай) Пирамида Фибоначчи (амортизирован ное время) М АКЕ _Н ЕАР θ(1) I NSERT θ(lg n)O(lg n)θ(1) M INIMUM θ(1)O(lg n)θ(1) E XTRACT _M IN θ(lg n)0(lg n)O(lg n) U NION θ(n)Ω(lg n)θ(1) D ECREASE JC EY θ(lg n) θ(1) D ELETE θ(lg n)v(lg n)O(lg n)

4 Биномиальные деревья Биномиальное дерево (binomial tree) Вк представляет собой рекурсивно определенное упорядоченное дерево. Биномиальное дерево Во состоит из одного узла. Биномиальное дерево Вк состоит из двух биномиальных деревьев Вк-1 связанных вместе: корень одного из них является крайним левым дочерним узлом корня второго дерева. Некоторые свойства биномиальных деревьев Биномиальное дерево Вк 1. имеет 2 к узлов; 2. имеет высоту к; 3. имеет корень степени к; степень всех остальных вершин меньше степени корня биномиального дерева. Кроме того, если дочерние узлы корня про­нумеровать слева направо числами к 1, к 2,..., 0, то i-й дочерний узел корня является корнем биномиального дерева Д.

5

6 Биномиальные пирамиды Биномиальная пирамида (binomial heap) Н представляет собой множество биномиальных деревьев, которые удовлетворяют следующим свойствам биномиальных пирамид. Каждое биномиальное дерево в Н подчиняется свойству неубывающей пирамиды (min-heap property): ключ узла не меньше ключа его родительского узла. Утверждается, что такие деревья являются упорядоченными в соответствии со свойством неубывающей пирамиды (min-heap-ordered). Для любого неотрицательного целого к имеется не более одного биномиального дерева Н, чей корень имеет степень к.

7 Биномиальная пирамида с 13 узлами

8 Представление биномиальных пирамид Каждое биномиальное дерево в биномиальной пирамиде хранится в представлении с левым дочерним и правым сестринским узлами. Каждый узел имеет поле key и содержит сопутствующую информацию, необходимую для работы приложения. Кроме того, каждый узел содержит указатель р [x] на родительский узел, указатель child [х] на крайний левый дочерний узел и указатель sibling [х] на правый сестринский по отношению к х узел. Если х корневой узел, то р [х] = NIL. Если узел х не имеет дочерних узлов, то child [х] = NIL, а если х самый правый дочерний узел своего родителя, то sibling [x] = NIL. Каждый узел ж, кроме того, содержит поле degree [x], в котором хранится количество дочерних узлов x.

9 Корни биномиальных деревьев внутри биномиальной пирамиды организованы в виде связанного списка, который мы будем называть списком корней (root list). При проходе по списку степени корней находятся в строго возрастающем порядке. Поле sibling имеет различный смысл для корней и для прочих узлов. Если х корень, то sibling [x] указывает на следующий корень в списке (как обычно, если х последний корень в списке, то sibling [x] = NIL). Обратиться к данной биномиальной пирамиде Н можно при помощи поля head [H], которое представляет собой указатель на первый корень в списке корней H. Если биномиальная пирамида не содержит элементов, то head [Н] = NIL.

10 Поиск минимального ключа Процедура Binomial_Heap_Minimum возвращает указатель на узел с минимальным ключом в биномиальной пирамиде Н с n узлами. В данной реализации предполагается, что в биномиальной пирамиде отсутствуют ключи, равные. B INOMIAL _H EAP _M INIMUM (H) 1. у NIL 2. х head [Н] 3. min 4. while х NIL 5. do if кеу[х] < min 6. then min key[x] 7. у x 8. x sibling [x] 9. return у

11 Слияние двух биномиальных пирами Операция по слиянию двух биномиальных пирамид используется в качестве подпрограммы в большинстве остальных операций. Процедура B INOMIAL _H EAP _ U NION многократно связывает биномиальные деревья с корнями одинаковой степени. Приведенная далее процедура связывает дерево В к-1 с корнем у с деревом Bk-1 с корнем z, делая z родительским узлом для у, после чего узел z становится корнем дерева Bk. BlNOMIAL_LlNK(y, z) 1.р[у] z 2. sibling [у] child[z] 3.child[z] у 4.degree[z] degree[z] + 1

12 Процедура B INOMIAL _L INK делает узел у новым заголовком связанного списка дочерних узлов узла z за время 0(1). Работа процедуры основана на том, что представление с левым дочерним и правым сестринским узлами каждого бино­ миального дерева отвечают свойству упорядоченности дерева: в биномиальном дереве Bk крайний левый дочерний узел корня является корнем биномиального дерева Bk-1. Приведенная далее процедура сливает биномиальные пирамиды Н 1 и H 2, возвращая получаемую в результате биномиальную пирамиду, причем в процессе слияния представления биномиальных пирамид Н 1 и H 2 уничтожаются. Помимо процедуры Binomial_Link, данная процедура использует вспомогательную процедуру Вinomial_Heap_Merge, которая объединяет списки корней Н 1 и H 2 в единый связанный список, отсортированный по степеням в монотонно возрастающем порядке.

13 Binomial_Heap_Union(Н 1, H 2 ) 1. H Make_Binomial_Heap() 2.head[H] Binomial_Heap_Merge(Н 1, H 2 ) 3. Освобождение объектов Н 1 и H 2, но не списков, на которые они указывают 4. if head[H] = NIL 5. then return H 6.prev_x NIL 7. x head[H] 8.next_x sibling[x] 9. while next_x NIL 10. do if (degree[x] degree[next_x]) или (sibling[next_x] NIL и degree[sibling[next_x]] = degree[x]) 11. then prev-x х// Случаи 1 и х next_x//Случаи 1 и 2

14 10. else if кеу[х] key[next_x] 11. then sibling[x] sibling[next_x] // Случай Binomial_Link(next_x, x) //Случай else if prev_x = NIL // Случай then head[H] next_x //Случай else sibling [prev_x] next_x //Случай BlNOMIAL_LlNK(x, next_x) //Случай x next_x //Случай next_x sibling [x] 19. return H

15

16

17 На рис. а показаны исходные биномиальные пирамиды Н1 и Н2. Рис. б иллюстрирует биномиальную пирамиду Я, которая является результатом работы процедуры Binomial_Heap_Merge(Н 1, H 2 ). Изначально х является первым корнем в списке корней H. Поскольку и x, и next_x имеют степень 0, и key [x] < key [next_x], реализуется случай 3. После связывания, x является первым из трех корней с одной и той же степенью, так что реализуется случай 2. После того как все указатели сдвигаются на одну позицию в списке корней (рис. г), реализуется случай 4 (x является первым из двух корней равной степени). После связывания реализуется случай 3 (рис. 19.4Д). После очередного связывания степень x становится равной 3, а степень next_x 4, так что реализуется случай 1 (рис. e). Эта итерация цикла последняя, поскольку после очередного перемещения указателей next_x становится равным nil.

18 Процедура B INOMIAL _H EAP _U NION имеет две фазы. Первая фаза осуществляется вызовом процедуры B INOMIAL _H EAP _M ERGE, объединяет списки корней биномиальных пирамид Н1 и Н2 в единый связанный список H, который отсортирован по степеням корней в монотонно возрастающем порядке. Однако в списке может оказаться по два (но не более) корня каждой степени, так что вторая фаза связывает корни одинаковой степени до тех пор, пока все корни не будут иметь разную степень. Поскольку связанный список H отсортирован по степеням, все операции по связыванию выполняются достаточно быстро. Более подробно процедура работает следующим образом. Процедура начинается с объединения в строках 1-3 списков корней биномиальных пирамид Н1 и Н2 в единый список корней H. Списки корней Н1 и Н2 отсортированы в строго возрастающем порядке; процедура B INOMIAL _H EAP _M ERGE возвращает список корней H, который также отсортирован в строго возрастающем порядке степеней корней. Если списки корней Н1 и Н2 содержат всего m корней, то время работы процедуры B INOMJAL _H EAP _M ERGE составляет О (m). Процедура на каждом шаге сравнивает корни в начале двух списков корней и добавляет в результирующий список корень с меньшей степенью, удаляя его из исходного списка.

19 Затем процедура Binomial_Heap_Union инициализирует ряд указателей в списке корней Н. В случае, если происходит слияние двух пустых биномиальных пирамид, в строках 4-5 выполняется возврат пустой биномиальной пирамиды. Начиная со строки 6, нам известно, что в биномиальной пирамиде Н имеется по крайней мере один корень. В процедуре поддерживаются три указателя внутрь списка корней. х указывает на текущий корень. prev_x указывает на корень, предшествующий х в списке корней: sibling [prev_x] = х. Поскольку изначально х не имеет предшественника, мы начинаем работу со значения prev_x, равного NIL. next_x указывает на корень, следующий в списке корней за х: sibling [х] = next_x.

20 Изначально в списке корней Н имеется не более двух узлов с данной степенью: поскольку Н1 и H2 были биномиальными пирамидами, каждая из них имела не более одного корня данной степени. Кроме того, процедура Binomial_Heap_Merge гарантирует, что если два корня в Н имеют одну и ту же степень, то эти корни соседствуют в списке корней. В действительности, в процессе работы Binomial_Heap_Union В некоторый момент в списке корней Н могут оказаться три корня данной степени вскоре вы увидите, как может реализоваться такая ситуация. При каждой итерации цикла while в строках 9-21, мы должны решить, следует ли связывать х и next_x, учитывая их степени и, возможно, степень sibling [next_x]. Инвариантом цикла является то, что в начале каждого выполнения тела цикла и x, и next_x не равны NIL.

21 Случай 1, показанный на а, реализуется, когда degree [х] degree [next_x], т.е. когда х является корнем Bk-дерева, a next_x корнем Вl-дерева, причем I > к. Эта ситуация обрабатывается в строках Мы не связываем х и next_x, так что мы просто смещаем указатели на одну позицию по списку. Обновление указателя next_x, который указывает на корень, следующий за х, выполняется в строке 21, поскольку это действие общее для всех случаев. Случай 2 (рис. б) реализуется, когда х является первым из трех корней с одинаковой степенью, т.е. когда degree [х] = degree [next_x] = degree [sibling [next_x]]. Эта ситуация обрабатывается так же, как и случай 1 мы просто перемещаем указатели по списку. В следующей итерации цикла будет обработан случай 3

22 или 4, когда объединяются второй и третий из трех корней с одинаковой степенью. В строке 10 выполняется проверка реализации случаев 1 и 2, а в строках их обработка. Случаи 3 и 4 реализуются, когда х представляет собой первый из двух корней одинаковой степени, т.е. когда degree [х] = degree [next_x] degree [sibling [next_x]]. Эти случаи могут возникнуть на любой итерации, в частности, всегда непосред­ственно после обнаружения случая 2. В случаях 3 и 4 мы связываем х и next_x. Различие между случаями 3 и 4 определяется тем, какой из этих узлов имеет меньший ключ и, соответственно, будет выступать в роли нового корня после связывания. В случае 3 (e) key [x] < key [next_x], поэтому next_x привязывается к ж. В строке 14 происходит удаление next_x из списка корней, а в строке 15 next_x становится крайним левым дочерним узлом х. В случае 4, показанном на рис. г, next_x имеет меньший ключ, так что х привязывается к next_x. В строках происходит удаление х из списка корней;

23

24 в зависимости от того, является х первым элементом списка (строка 17) или нет (строка 18). В строке 19 х делается крайним слева дочерним узлом next-x, а в строке 20 происходит обновление х для следующей итерации. Настройки для следующей итерации цикла while после случаев 3 и 4 оди­наковы. Мы должны просто связать два -дерева в -дерево, на которое указывает х. После него в списке может находиться от нуля до двух Bk+i-дере­вьев, так что х теперь указывает на первое в последовательности из одного, двух или трех Bk+i -деревьев в списке корней. Если дерево только одно, на следующей итерации мы получаем случай 1: degree [ж] ф degree [next-x]. Если х первое из двух деревьев, то на следующей итерации получаются случаи 3 или 4. И наконец, если х первое из трех деревьев, то в следующей итерации получаем случай 2. Время работы процедуры B INOMIAL _H EAP _U NION равно О (lgn), где п об­щее количество узлов в биномиальных пирамидах Н\ и Яг.

25 Вставка узла Приведенная далее процедура вставляет узел х в биномиальную пирамиду Н (предполагается, что для х уже выделена память и поле key [ж] уже заполнено): Binomial_Heap_Insert(H, х) 1.Н' M AKE _B INOMIAL _H EAP () 2.р[х) NIL 3.child[x] NIL 4.sibling[x] NIL 5. degree[x] 0 6.head[H'] x 7. H B INOMIAL _H EAP _U NION (H, H') Процедура просто создает биномиальную пирамиду H' с одним узлом за вре­мя 0(1) и объединяет ее с биномиальной пирамидой Я, содержащей п узлов, за время О (lg n). Вызов B INOMIAL _H EAP _U NION должен освободить память, вы­деленную для временной биномиальной пирамиды H'.

26 Извлечение вершины с минимальным ключом Приведенная ниже процедура извлекает узел с минимальным ключом из биномиальной пирамиды H и возвращает указатель на извлеченный узел: B INOMIAL _H EAP _E XTRACT _M IN (H) 1. Поиск корня х с минимальным значением ключа в списке корней H, и удаление х из списка корней H 2.H' Make_Binomial_Heap() 3. Обращение порядка связанного списка дочерних узлов х, установка поля р каждого дочернего узла равным NIL и присвоение указателю head[H] адреса заголовка получающегося списка 4. H B INOMIAL _H EAP _U NION (H, H') 5. return х

27

28 Работа процедуры B INOMIAL _H EAP _E XTRACT _M IN

29 Уменьшение ключа Приведенная далее процедура уменьшает значение ключа узла х в биномиальной пирамиде Н, присваивая ему новое значение к. В случае, если значение к превышает текущий ключ х, процедура сообщает об ошибке. B INOMIAL _H EAP _D ECREASE _K EY (H, х, к) 1. if к > кеу[х] 2. then error Новый ключ больше текущего 3.кеу[х] к 4. у х 5. z р[у] 6. while z nil и key [у] < key[z] 7. do Обменять key [у] key[z] // Если у и z содержат сопутствующую //информацию, обменять также и ее 8. у z 9. z р[у]

30

31 данная процедура уменьшает значение ключа так же, как и в бинарной неубывающей пирамиде путем всплывания ключа в пирамиде. После того, как мы убедимся, что новый ключ не превышает текущий, и присвоим его х, процедура идет вверх по дереву. Изначально значение у равно х. В каждой итерации цикла while в строках 6-8 значение key [у] сравнивается со значением ключа родительского по отношению к у узла z. Если у является корнем или key [у] key [z], биномиальное дерево является упорядоченным в соответствии со свойством неубывающей пирамиды. В противном случае узел у нарушает свойство неубывающей пирамиды и происходит обмен ключами и сопутствующими данными между узлами у и z, после чего процедура присваивает переменной у значение z ив очередной итерации переходит на один уровень вверх. Процедура B INOMIAL _H EAP _D ECREASE _K EY выполняется за время O(lg n).

32 Удаление ключа Удаление ключа х и сопутствующей информации из биномиальной пирамиды Н легко выполняется за время O(lg n). В приведенной ниже реализации этой операции предполагается, что ни один узел в биномиальной пирамиде не имеет ключ со значением Binomial_Heap_Delete(H, х) 1.Binomial_Heap_Decrease_Key(H, х, -) 2.Binomial_Heap_Extract_Min(H) Процедура B INOMIAL _H EAP _D ECREASE _K EY делает узел х единственным узлом с минимальным ключом в биномиальной пирамиде, равным. Затем этот ключ и связанные с ним сопутствующие данные всплывают в биномиальной пирамиде до корня в процедуре Bino- mial_Heap_Decrease_Key, после чего этот корень удаляется из дерева вызовом процедуры B INOMIAL _H EAP _E XTRACT _M IN. Время работы процедуры B INOMIAL _H EAP _D ELETE равно О (lg п).