Операція | Амортизаційний час |
---|---|
Make-Heap | |
Insert | |
Minimum | |
Extract-Min | |
Union | |
Decrease-Key | |
Delete |
Купа Фібоначчі — структура даних, ефективна реалізація черги з пріоритетом.
З теоретичної точки зору купи Фібоначчі особливо варто використовувати, коли кількість Extract-Min і Delete операцій мала порівняно з кількістю інших операцій. Наприклад, деякі алгоритми на графах можуть викликати Decrease-Key на кожному ребрі. Для щільного графу (сталий) амортизаційний час кожного виклику Decrease-Key складається у велику перевагу в порівнянні з логарифмічним часом у найгіршому випадку в бінарній купі. Це можна побачити на прикладі алгоритмів про найкоротші шляхи з одного входу і мінімального кістякового дерева. З практичної точки зору сталий множник прихований у складності алгоритму і складність у програмуванні купи Фібоначчі роблять її менш бажаною, ніж звичайну бінарну або d-арну купу для більшості застосувань.
Історія
Фібоначчієву купу запропонували Фредман і Тар'ян у 1984 році. Головним гаслом цієї конструкції було «ми виконуємо роботу лише коли мусимо, і тоді ми використовуємо це для спрощення структури настільки наскільки можливо, таким чином, щоб майбутня робота була легкою».
Структура купи
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODBMelExTDBacFltOXVZV05qYVY5b1pXRndMbkJ1Wnk4eU5UQndlQzFHYVdKdmJtRmpZMmxmYUdWaGNDNXdibWM9LnBuZw==.png)
Купа Фібоначчі являє собою набір дерев, кожне з яких є мінкупою змінної арності з такими властивостями:
- Вузли дерев відповідають елементам, що зберігаються в черзі.
- Корені куповпорядкованих дерев поєднані у двобічно зв'язаний список.
- Зберігається вказівник на корінь дерева, який відповідає елементу з найменшим ключем (варто зауважити, що те, що кожне дерево є мінкупою, гарантує, що цей елемент буде коренем одного з дерев).
- Для кожного вузла зберігається його ранг (степінь), тобто кількість його дітей, а також чи він позначений (мету позначення ми визначимо пізніше).
- Вимога розміру: якщо вузол u має степінь k, то піддерево з коренем u має щонайменше
вузлів, де
— це i-те число Фібоначчі, тобто
і
для
Кожен вузол x містить вказівник x.p на свого предка і вказівник x.child на один із його нащадків. Нащадки зв'язані в циклічний двобічно зв'язаний список. Кожен нащадок y має вказівники y.left та y.right. Якщо вузол є єдиним нащадком, тоді y = y.left = y.right. Нащадки елемента можуть перебувати у будь-якому порядку. Використання двобічно зв'язаних списків уможливлює вставляння і видалення елементів за час O(1), а також зв'язування двох списків за O(1). Також кожен вузол має атрибут x.degree, що дорівнює кількості нащадків, і атрибут x.mark, що показує, чи втратив вузол нащадка з моменту, як він став нащадком свого поточного предка.
Доступ до купи відбувається через вказівник H.min, який вказує на корінь дерева з найменшим ключем. Якщо дерево порожнє, то H.min дорівнює NIL.
Для оцінки швидкості використовують (метод потенціалів) із потенціальною функцією Де
дає кількість дерев у купі, а
— кількість позначених вузів.
- Максимальний степінь
Надалі вважатимемо, що нам відома верхня межа D(n) максимального степеня вузла у Фібоначчієвій купі з n вузлами. Якщо купа підтримує лише операції поєднуваної купи, тоді Хоча, навіть якщо Фібоначчієва купа підтримує Decrease-Key та Delete, то
Операції
INSERT
Вставка дужа проста: додаємо новий елемент s як нову мінкупу в колекцію і перевіряємо, чи k(s) менше за поточне найменше значення. Якщо так, то відповідно змінюємо вказівник H.min.
Insert(H, x) 1 x.degree = 0 2 x.p = NIL 3 x.child = NIL 4 x.mark = FALSE 5 якщо H.min == NIL 6 створити список коренів для H, що містить лише x 7 H.min = x 8 інакше вставити x у список коренів H 9 якщо x.key < H.min.key 10 H.min = x 11 H.n = H.n + 1
Щоб визначити амортизаційну вартість вставляння елемента, нехай H буде початковою Фібоначчієвою купою і H' буде результовною. Тоді і
отже збільшення потенціалу становить
Оскільки амортизаційна вартість дорівнює сумі дійсної вартості і різниці потенціалів, то вона дорівнює
DECREASE-KEY
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHdMekE1TDBacFltOXVZV05qYVY5b1pXRndMV1JsWTNKbFlYTmxhMlY1TG5CdVp5OHlOVEJ3ZUMxR2FXSnZibUZqWTJsZmFHVmhjQzFrWldOeVpXRnpaV3RsZVM1d2JtYz0ucG5n.png)
Коли ми зменшуємо ключ елемента s, якщо умови мінкупи все ще задовільняються, то нам більше не потрібно робити нічого. Інакше, ми просто відтинаємо піддерево з коренем в s і вставляємо його як нове піддерево у колекцію. Ми порівнюємо новий ключ s із попереднім мінімальним елементом і змінюємо вказівник H.min відповідно.
Таким чином, ми отримуємо щось, що виглядає подібно до бажаної Фібоначчієвої купи. Однак, проблема із простим відтинанням кожного такого s полягає в тому, що ми можемо врешті решт порушити вимогу розміру. Отже, щоб полегшити ситуацію, ми впроваджуємо додаткове правило, що коли ми відтинаємо s ми перевіряємо, чи не помічений його батьківський елемент. Якщо так, то ми також відтинаємо батьківській елемент і знімаємо позначку з нього. Інакше, ми просто позначаємо батьківський елемент. Перевірка батьківського елемента виконується рекурсивно, тобто, якщо батько батька позначений, ми відтинаємо і його також. Очевидно, що якщо ми відтинаємо корінь, то ми не робимо нічого, тому немає сенсу позначати корінь. Тому, ця потенційно каскадна процедура, завжди завершується.
Decrease-Key(H,x,k) 1 якщо k > x.key 2 помилка "новий ключ більший ніж попередній" 3 x.key = k 4 y = x.p 5 якщо y != NIL і x.key < y.key 6 Cut(H,x,y) 7 Cascading-Cut(H,y) 8 якщо x.key < H.min.key 9 H.min = x
Cut(H,x,y) 1 видалити x зі списку дітей y, зменшити y.degree 2 додати до списку коренів H 3 x.p = NIL 4 x.mark = FALSE
Cascading-Cut(H,y) 1 z = y.p 2 якщо z != NIL 3 якщо y.mark == FALSE 4 y.mark = TRUE 5 інакше Cut(H,y,z) 6 Cascading-Cut(H,z)
З'ясуємо дійсну вартість зменшення ключа. Decrease-Key потребує O(1), не враховуючи каскадного видалення. Припустимо, що відбулось c викликів Cascading-Cut. Виконання кожного Cascading-Cut, не враховуючи рекурсивних викликів, потребує O(1). Отже дійсна вартість Decrease-Key становить O(c).
Тепер обчислимо різницю потенціалів. У висліді зменшення ключа утворюється c-1 нових дерев через каскадні відтинання і дерево з коренем x. c-1 вузів припиняють бути позначеними. І, можливо, позначається один вузол.
З цього випливає, що амортизаційна вартість буде не більше ніж
EXTRACT-MIN
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODFMelUyTDBacFltOXVZV05qYVY5b1pXRndYMlY0ZEhKaFkzUnRhVzR4TG5CdVp5OHhOekJ3ZUMxR2FXSnZibUZqWTJsZmFHVmhjRjlsZUhSeVlXTjBiV2x1TVM1d2JtYz0ucG5n.png)
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODVMemsxTDBacFltOXVZV05qYVY5b1pXRndYMlY0ZEhKaFkzUnRhVzR5TG5CdVp5OHhNekJ3ZUMxR2FXSnZibUZqWTJsZmFHVmhjRjlsZUhSeVlXTjBiV2x1TWk1d2JtYz0ucG5n.png)
Насамкінець, ми можемо описати видобування мінімального елемента s*. Починаємо з видалення s* (на нього вказує H.min) і додавання усіх його дітей як дерев у колекцію. Тепер, ми продивляємось усю колекцію, знаходимо найменший елемент і оновлюємо H.min відповідно.
На цьому можна було б і завершити, оскільки ми отримали правильну Фібоначчієву купу. Однак, не складно побачити, що досі описані операції над купою, роблять список коренів довшим і довшим. Отже, проходження через увесь список коренів ставатиме обчислювально дорожчим. Отже, якщо ми вже маємо зробити якусь роботу у будь-якому випадку, то ми виконаємо очищення зараз, щоб уникнути більшої роботи у наступному. Тому, доти доки наявні два дерева з однаковим рангом, скажімо k, ми зливаємо ці дерева, щоб отримати дерево рангу k+1. Злиття полягає у порівнянні коренів і додавання дерева з більшим коренем як дочірнього до другого кореня. Зауважимо, що оскільки злиття може створити друге дерево рангу k+1 у колекції, один корінь може взяти участь у кількох злиттях.
Extract-Min(H) 1 z = H.min 2 якщо z != NIL 3 для кожної дитини x z 4 додати x до списку коренів H 5 x.p = NIL 6 видалити z зі списку коренів H 7 якщо z == z.right // Вважаємо, що видалення z із двобічного списку не змінює її right/left вказівників 8 H.min = NIL 9 інакше H.min = z.right 10 Consolidate(H) 11 H.n = H.n - 1 12 повернути z
Після видалення z ми консолідуємо список коренів H. Консолідація відбувається виконуючи наступні кроки допоки у списку коренів присутні корені з однаковим степенем.
- Знайти два корені x, y з однаковим степенем. Припустимо, без втрати загальності, що x.key =< y.key.
- Приєднуємо y до x. Тут ми збільшуємо x.degree і очищаємо позначку на y.
Consolidate(H) 1 нехай A[0..D(H.n)] буде новим масивом 2 для i = 0 до D(H.n) 3 A[i] = NIL 4 для кожного вузла w у списку коренів H 5 x = w 6 d = x.degree 7 поки A[d] != NIL 8 y = A[d] // Інший корінь з тим самим степенем як і x 9 якщо x.key > y.key 10 обміняти x і y 11 Heap-Link(H,y,x) 12 A[j] = NIL 13 d = d + 1 14 A[d] = x 15 H.min = NIL 16 для i = 0 до D(H.n) 17 якщо A[i] != NIL 18 якщо H.min == NIL 19 створити список коренів для H, що містить лише A[i] 20 H.min = A[i] 21 інакше вставити A[i] у список коренів H 22 якщо A[i].key < H.min.key 23 H.min = A[i]
Heap-Link(H,y,x) 1 видалити y зі списку коренів H 2 зробити y дочірнім для x, збільшити x.degree 3 y.mark = FALSE
Обчислимо дійсну вартість видобування найменшого елемента. O(D(n)) маємо завдяки Extract-Min, через необхідність обробити усі дочірні вузли, і завдяки циклам 2-3 і 16-23 у Consolidate. Розглянемо внесок циклу 4-14 Consolidate, для цього використаємо (груповий аналіз). Розмір списку коренів перед викликом Consolidate не більше ніж D(n) + t(H) + 1. Ми знаємо, що кожен раз у тілі циклу while один з коренів приєднується до іншого, отже, загальна кількість ітерацій циклу while у всіх ітераціях зовнішнього циклу for не може перевищити розмір списку коренів. Тому загальна кількість роботи у циклі 4-14 щонайбільше пропорційна до D(n) + t(H). Отже, всього нам треба O(D(n) + t(H)).
Потенціал перед видобуванням мінімального вузла є t(H) + 2m(H), а після — не більше ніж D(n) + 1. З цього і дійсної вартості маємо амортизаційну вартість
Обмеження на найбільший степінь
Лема. Нехайце вузол, і нехай
позначають його дітей у порядку в якому вони були додані до
Тоді:
Доведення: Очевидно, що y1.degree ≥ 0. Для i ≥ 2, коли ми yi додавали до x, там вже було щонайменше i-1 дочірніх елементів, значить на момент додавання степінь yi мав дорівнювати степеню x. З того часу один з дочірніх елементів y міг бути відрізаним. Отже, степінь yi міг зменшитись на 1 і стати i-2.∎
Факти про числа Фібоначчі: 1.2.
де
![]()
Лема. Нехай x буде вузлом у купі Фібоначчі і нехай k = x.degree. Тоді size(x) ≥ Fk+2 ≥ φk.
Наслідок: Найбільший степінь D(n) будь-якого вузла в n-вузловій Фібоначчієвій купі є O(lg n). Доведення: Нехай x буде довільним вузлом і k=x.degree. Маємо, що n ≥ size(x) ≥ φk. Логарифмуючи з основою φ отримуємо k ≤ logφn. Оскільки k ціле, то∎
Джерела
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 19 Фібоначчієві купи. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
- Fibonacci Heaps на www.cs.princeton.edu
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Operaciya Amortizacijnij chasMake Heap 8 1 displaystyle Theta 1 Insert 8 1 displaystyle Theta 1 Minimum 8 1 displaystyle Theta 1 Extract Min O lg n displaystyle O lg n Union 8 1 displaystyle Theta 1 Decrease Key 8 1 displaystyle Theta 1 Delete O lg n displaystyle O lg n Kupa Fibonachchi struktura danih efektivna realizaciya chergi z prioritetom Z teoretichnoyi tochki zoru kupi Fibonachchi osoblivo varto vikoristovuvati koli kilkist Extract Min i Delete operacij mala porivnyano z kilkistyu inshih operacij Napriklad deyaki algoritmi na grafah mozhut viklikati Decrease Key na kozhnomu rebri Dlya shilnogo grafu stalij amortizacijnij chas 8 1 displaystyle Theta 1 kozhnogo vikliku Decrease Key skladayetsya u veliku perevagu v porivnyanni z logarifmichnim chasom 8 lg n displaystyle Theta lg n u najgirshomu vipadku v binarnij kupi Ce mozhna pobachiti na prikladi algoritmiv pro najkorotshi shlyahi z odnogo vhodu i minimalnogo kistyakovogo dereva Z praktichnoyi tochki zoru stalij mnozhnik prihovanij u skladnosti algoritmu i skladnist u programuvanni kupi Fibonachchi roblyat yiyi mensh bazhanoyu nizh zvichajnu binarnu abo d arnu kupu dlya bilshosti zastosuvan IstoriyaFibonachchiyevu kupu zaproponuvali Fredman i Tar yan u 1984 roci Golovnim gaslom ciyeyi konstrukciyi bulo mi vikonuyemo robotu lishe koli musimo i todi mi vikoristovuyemo ce dlya sproshennya strukturi nastilki naskilki mozhlivo takim chinom shob majbutnya robota bula legkoyu Struktura kupiZobrazhennya 1 Priklad Fibonachchiyevoyi kupi Kupa maye tri dereva stepeniv 0 1 i 3 Tri poznacheni vershini sinim Otzhe potencial kupi stanovit 9 3 dereva 2 3 poznachenih vershini Kupa Fibonachchi yavlyaye soboyu nabir derev kozhne z yakih ye minkupoyu zminnoyi arnosti z takimi vlastivostyami Vuzli derev vidpovidayut elementam sho zberigayutsya v cherzi Koreni kupovporyadkovanih derev poyednani u dvobichno zv yazanij spisok Zberigayetsya vkazivnik na korin dereva yakij vidpovidaye elementu z najmenshim klyuchem varto zauvazhiti sho te sho kozhne derevo ye minkupoyu garantuye sho cej element bude korenem odnogo z derev Dlya kozhnogo vuzla zberigayetsya jogo rang stepin tobto kilkist jogo ditej a takozh chi vin poznachenij metu poznachennya mi viznachimo piznishe Vimoga rozmiru yaksho vuzol u maye stepin k to pidderevo z korenem u maye shonajmenshe Fk 2 displaystyle F k 2 vuzliv de Fi displaystyle F i ce i te chislo Fibonachchi tobto F0 0 F1 1 displaystyle F 0 0 F 1 1 i Fi Fi 1 Fi 2 displaystyle F i F i 1 F i 2 dlya i 2 displaystyle i geq 2 Kozhen vuzol x mistit vkazivnik x p na svogo predka i vkazivnik x child na odin iz jogo nashadkiv Nashadki zv yazani v ciklichnij dvobichno zv yazanij spisok Kozhen nashadok y maye vkazivniki y left ta y right Yaksho vuzol ye yedinim nashadkom todi y y left y right Nashadki elementa mozhut perebuvati u bud yakomu poryadku Vikoristannya dvobichno zv yazanih spiskiv umozhlivlyuye vstavlyannya i vidalennya elementiv za chas O 1 a takozh zv yazuvannya dvoh spiskiv za O 1 Takozh kozhen vuzol maye atribut x degree sho dorivnyuye kilkosti nashadkiv i atribut x mark sho pokazuye chi vtrativ vuzol nashadka z momentu yak vin stav nashadkom svogo potochnogo predka Dostup do kupi vidbuvayetsya cherez vkazivnik H min yakij vkazuye na korin dereva z najmenshim klyuchem Yaksho derevo porozhnye to H min dorivnyuye NIL Dlya ocinki shvidkosti vikoristovuyut metod potencialiv iz potencialnoyu funkciyeyu F H t H 2m H displaystyle Phi H t H 2m H De t H displaystyle t H daye kilkist derev u kupi a m H displaystyle m H kilkist poznachenih vuziv Maksimalnij stepin Nadali vvazhatimemo sho nam vidoma verhnya mezha D n maksimalnogo stepenya vuzla u Fibonachchiyevij kupi z n vuzlami Yaksho kupa pidtrimuye lishe operaciyi poyednuvanoyi kupi todi D n lg n displaystyle D n leq lfloor lg n rfloor Hocha navit yaksho Fibonachchiyeva kupa pidtrimuye Decrease Key ta Delete to D n O lg n displaystyle D n O lg n OperaciyiINSERT Vstavka duzha prosta dodayemo novij element s yak novu minkupu v kolekciyu i pereviryayemo chi k s menshe za potochne najmenshe znachennya Yaksho tak to vidpovidno zminyuyemo vkazivnik H min Insert H x 1 x degree 0 2 x p NIL 3 x child NIL 4 x mark FALSE 5 yaksho H min NIL 6 stvoriti spisok koreniv dlya H sho mistit lishe x 7 H min x 8 inakshe vstaviti x u spisok koreniv H 9 yaksho x key lt H min key 10 H min x 11 H n H n 1 Shob viznachiti amortizacijnu vartist vstavlyannya elementa nehaj H bude pochatkovoyu Fibonachchiyevoyu kupoyu i H bude rezultovnoyu Todi t H t H 1 displaystyle t H t H 1 i m H M H displaystyle m H M H otzhe zbilshennya potencialu stanovit t H 1 2m H t H 2m H 1 displaystyle t H 1 2m H t H 2m H 1 Oskilki amortizacijna vartist dorivnyuye sumi dijsnoyi vartosti i riznici potencialiv to vona dorivnyuye O 1 1 O 1 displaystyle O 1 1 O 1 DECREASE KEY Fibonachchiyeva kupa iz zobrazhennya 1 pislya zmenshennya klyucha z 9 do 0 Cej vuzol yak i dva jogo poznacheni poperedniki vidtinayutsya vid dereva z korenem 1 i roztashovuyutsya yak novi koreni Koli mi zmenshuyemo klyuch elementa s yaksho umovi minkupi vse she zadovilnyayutsya to nam bilshe ne potribno robiti nichogo Inakshe mi prosto vidtinayemo pidderevo z korenem v s i vstavlyayemo jogo yak nove pidderevo u kolekciyu Mi porivnyuyemo novij klyuch s iz poperednim minimalnim elementom i zminyuyemo vkazivnik H min vidpovidno Takim chinom mi otrimuyemo shos sho viglyadaye podibno do bazhanoyi Fibonachchiyevoyi kupi Odnak problema iz prostim vidtinannyam kozhnogo takogo s polyagaye v tomu sho mi mozhemo vreshti resht porushiti vimogu rozmiru Otzhe shob polegshiti situaciyu mi vprovadzhuyemo dodatkove pravilo sho koli mi vidtinayemo s mi pereviryayemo chi ne pomichenij jogo batkivskij element Yaksho tak to mi takozh vidtinayemo batkivskij element i znimayemo poznachku z nogo Inakshe mi prosto poznachayemo batkivskij element Perevirka batkivskogo elementa vikonuyetsya rekursivno tobto yaksho batko batka poznachenij mi vidtinayemo i jogo takozh Ochevidno sho yaksho mi vidtinayemo korin to mi ne robimo nichogo tomu nemaye sensu poznachati korin Tomu cya potencijno kaskadna procedura zavzhdi zavershuyetsya Decrease Key H x k 1 yaksho k gt x key 2 pomilka novij klyuch bilshij nizh poperednij 3 x key k 4 y x p 5 yaksho y NIL i x key lt y key 6 Cut H x y 7 Cascading Cut H y 8 yaksho x key lt H min key 9 H min x Cut H x y 1 vidaliti x zi spisku ditej y zmenshiti y degree 2 dodati do spisku koreniv H 3 x p NIL 4 x mark FALSE Cascading Cut H y 1 z y p 2 yaksho z NIL 3 yaksho y mark FALSE 4 y mark TRUE 5 inakshe Cut H y z 6 Cascading Cut H z Z yasuyemo dijsnu vartist zmenshennya klyucha Decrease Key potrebuye O 1 ne vrahovuyuchi kaskadnogo vidalennya Pripustimo sho vidbulos c viklikiv Cascading Cut Vikonannya kozhnogo Cascading Cut ne vrahovuyuchi rekursivnih viklikiv potrebuye O 1 Otzhe dijsna vartist Decrease Key stanovit O c Teper obchislimo riznicyu potencialiv U vislidi zmenshennya klyucha utvoryuyetsya c 1 novih derev cherez kaskadni vidtinannya i derevo z korenem x c 1 vuziv pripinyayut buti poznachenimi I mozhlivo poznachayetsya odin vuzol t H c 2 m H c 2 t H 2m H 4 c displaystyle t H c 2 m H c 2 t H 2m H 4 c Z cogo viplivaye sho amortizacijna vartist bude ne bilshe nizh O c 4 c O 1 displaystyle O c 4 c O 1 EXTRACT MIN Fibonachchiyeva kupa iz zobrazhennya 1 pislya pershoyi fazi viluchennya minimalnogo elementa Vuzol z klyuchem 1 minimum bulo vidaleno i jogo diti buli dodani yak okremi dereva Fibonachchiyeva kupa iz zobrazhennya 1 pislya vikonannya viluchennya najmenshogo elementa Spershu poyednani vuzli 3 i 6 Potim rezultat poyednanij iz derevom z korenem u vuzli 2 Nasamkinec znajdeno novij minimum Nasamkinec mi mozhemo opisati vidobuvannya minimalnogo elementa s Pochinayemo z vidalennya s na nogo vkazuye H min i dodavannya usih jogo ditej yak derev u kolekciyu Teper mi prodivlyayemos usyu kolekciyu znahodimo najmenshij element i onovlyuyemo H min vidpovidno Na comu mozhna bulo b i zavershiti oskilki mi otrimali pravilnu Fibonachchiyevu kupu Odnak ne skladno pobachiti sho dosi opisani operaciyi nad kupoyu roblyat spisok koreniv dovshim i dovshim Otzhe prohodzhennya cherez uves spisok koreniv stavatime obchislyuvalno dorozhchim Otzhe yaksho mi vzhe mayemo zrobiti yakus robotu u bud yakomu vipadku to mi vikonayemo ochishennya zaraz shob uniknuti bilshoyi roboti u nastupnomu Tomu doti doki nayavni dva dereva z odnakovim rangom skazhimo k mi zlivayemo ci dereva shob otrimati derevo rangu k 1 Zlittya polyagaye u porivnyanni koreniv i dodavannya dereva z bilshim korenem yak dochirnogo do drugogo korenya Zauvazhimo sho oskilki zlittya mozhe stvoriti druge derevo rangu k 1 u kolekciyi odin korin mozhe vzyati uchast u kilkoh zlittyah Extract Min H 1 z H min 2 yaksho z NIL 3 dlya kozhnoyi ditini x z 4 dodati x do spisku koreniv H 5 x p NIL 6 vidaliti z zi spisku koreniv H 7 yaksho z z right Vvazhayemo sho vidalennya z iz dvobichnogo spisku ne zminyuye yiyi right left vkazivnikiv 8 H min NIL 9 inakshe H min z right 10 Consolidate H 11 H n H n 1 12 povernuti z Pislya vidalennya z mi konsoliduyemo spisok koreniv H Konsolidaciya vidbuvayetsya vikonuyuchi nastupni kroki dopoki u spisku koreniv prisutni koreni z odnakovim stepenem Znajti dva koreni x y z odnakovim stepenem Pripustimo bez vtrati zagalnosti sho x key lt y key Priyednuyemo y do x Tut mi zbilshuyemo x degree i ochishayemo poznachku na y Consolidate H 1 nehaj A 0 D H n bude novim masivom 2 dlya i 0 do D H n 3 A i NIL 4 dlya kozhnogo vuzla w u spisku koreniv H 5 x w 6 d x degree 7 poki A d NIL 8 y A d Inshij korin z tim samim stepenem yak i x 9 yaksho x key gt y key 10 obminyati x i y 11 Heap Link H y x 12 A j NIL 13 d d 1 14 A d x 15 H min NIL 16 dlya i 0 do D H n 17 yaksho A i NIL 18 yaksho H min NIL 19 stvoriti spisok koreniv dlya H sho mistit lishe A i 20 H min A i 21 inakshe vstaviti A i u spisok koreniv H 22 yaksho A i key lt H min key 23 H min A i Heap Link H y x 1 vidaliti y zi spisku koreniv H 2 zrobiti y dochirnim dlya x zbilshiti x degree 3 y mark FALSE Obchislimo dijsnu vartist vidobuvannya najmenshogo elementa O D n mayemo zavdyaki Extract Min cherez neobhidnist obrobiti usi dochirni vuzli i zavdyaki ciklam 2 3 i 16 23 u Consolidate Rozglyanemo vnesok ciklu 4 14 Consolidate dlya cogo vikoristayemo grupovij analiz Rozmir spisku koreniv pered viklikom Consolidate ne bilshe nizh D n t H 1 Mi znayemo sho kozhen raz u tili ciklu while odin z koreniv priyednuyetsya do inshogo otzhe zagalna kilkist iteracij ciklu while u vsih iteraciyah zovnishnogo ciklu for ne mozhe perevishiti rozmir spisku koreniv Tomu zagalna kilkist roboti u cikli 4 14 shonajbilshe proporcijna do D n t H Otzhe vsogo nam treba O D n t H Potencial pered vidobuvannyam minimalnogo vuzla ye t H 2m H a pislya ne bilshe nizh D n 1 Z cogo i dijsnoyi vartosti mayemo amortizacijnu vartist O D n t H D n 1 2m H t H 2m H O D n O t H t H O D n displaystyle O D n t H D n 1 2m H t H 2m H O D n O t H t H O D n Obmezhennya na najbilshij stepinLema Nehaj x displaystyle x ce vuzol i nehaj y1 yk displaystyle y 1 dots y k poznachayut jogo ditej u poryadku v yakomu voni buli dodani do x displaystyle x Todi yi degree 0i 1i 2i 1 displaystyle y i degree geq begin cases 0 amp i 1 i 2 amp i geq 1 end cases Dovedennya Ochevidno sho y1 degree 0 Dlya i 2 koli mi yi dodavali do x tam vzhe bulo shonajmenshe i 1 dochirnih elementiv znachit na moment dodavannya stepin yi mav dorivnyuvati stepenyu x Z togo chasu odin z dochirnih elementiv y mig buti vidrizanim Otzhe stepin yi mig zmenshitis na 1 i stati i 2 Fakti pro chisla Fibonachchi 1 k 0 Fk 2 1 i 0kFi displaystyle forall k geq 0 F k 2 1 sum i 0 k F i 2 k 0 Fk 2 ϕk displaystyle forall k geq 0 F k 2 geq phi k de ϕ 1 5 2 displaystyle phi 1 sqrt 5 2 Lema Nehaj x bude vuzlom u kupi Fibonachchi i nehaj k x degree Todi size x Fk 2 fk Naslidok Najbilshij stepin D n bud yakogo vuzla v n vuzlovij Fibonachchiyevij kupi ye O lg n Dovedennya Nehaj x bude dovilnim vuzlom i k x degree Mayemo sho n size x fk Logarifmuyuchi z osnovoyu f otrimuyemo k logfn Oskilki k cile to k logϕ n displaystyle k leq lfloor log phi n rfloor DzherelaT Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 19 Fibonachchiyevi kupi Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 Fibonacci Heaps na www cs princeton edu