Gramada de Fibonacci
Heap Fibonacci ( ing. Fibonacci heap ) este o structură de date care este un set de arbori ordonați în conformitate cu proprietatea unei piramide nedescrescătoare. Mulțile Fibonacci au fost introduse de Michael Fredman și Robert Tarjan în 1984 .
Structura este o implementare a tipului de date abstracte „ Coadă prioritară ” și este remarcabilă prin faptul că operațiunile care nu necesită ștergere au un timp de rulare amortizat de (pentru un heap binar și un heap binomial , timpul de rulare amortizat este de ). Pe lângă operațiunile standard , , , heap-ul Fibonacci vă permite să efectuați operația de îmbinare a două heap-uri în timp. INSERTMINDECREASE-KEYUNION
Structura
- Mormanul Fibonacci este o colecție de copaci .
- Fiecare arbore din este supus proprietății heap ( eng. min-heap property ): cheia fiecărui nod nu este mai mică decât cheia nodului părinte.
- Fiecare nod din conține următoarele indicatoare și câmpuri:
- - câmpul în care este stocată cheia;
- — pointer către nodul părinte;
- — un pointer către unul dintre nodurile copil;
- - pointer către nodul soră stânga;
- - indicatorul către nodul soră din dreapta;
- - un câmp care stochează numărul de noduri copii;
- — o valoare booleană care indică dacă nodul a pierdut vreun nod copil de când a devenit un nod copil al unui alt nod.
- Nodurile copil sunt combinate cu ajutorul indicatorilor și într-o listă ciclică dublu legată de noduri copil (de exemplu , listă de copii ) .
- Rădăcinile tuturor copacilor din sunt conectate prin intermediul indicatorilor și într-o listă ciclică dublu legată de rădăcini ( eng. root list ).
- Pentru întregul heap Fibonacci, este stocat și un pointer către nodul cu cheia minimă , care este rădăcina unuia dintre arbori. Acest nod este numit nodul minim .
- Numărul curent de noduri în este stocat în .
![{\tasta de afișare[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97b36173e5d88ef517878d66a8682fab5bdbabbd)
![{\displaystyle p[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b81272b44de4208e118d4381df4c6828cb52da8)
![{\displaystyle copil[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7983ae8a15176fca40c69829753ebff7acd09cd)
![{\displaystyle stânga[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fa7823fa23979d95eb14ab7667a573c22e01b7a)
![{\displaystyle dreapta[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11d488d953d9ad638c15d2594ab597b5e653f15e)
![{\displaystyle grad[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fbb4e65cbfec576877633e2ad6ceaaaae241696)
![{\displaystyle mark[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/542b7e5368647a254202d3b202a71c2df4bf1954)
![{\displaystyle min[H]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9c75b5f06b71957bc80e0c4e56425cdf8f30b07)
![{\displaystyle n[H]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92ed2faefa5bfbe5a8314ec6f2b3b1ca9bc406c7)
Operațiuni
Crearea unui nou heap Fibonacci
Procedura Make_Fib_Heap returnează un obiect Fibonacci heap și = NULL. Nu sunt copaci .
![{\displaystyle n[H]=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6755b0e87ac6248f20059f3300df0f6cb90f896)
Costul amortizat al unei proceduri este egal cu costul real al acesteia .
Inserarea unui Nod
Fib_Heap_Insert 1 ← 0 2 ← NULL 3 ← NULL 4 ← 5 ← 6 ← FALS 7 Atașarea unei liste de rădăcini care conține , la o listă de rădăcini 8 dacă = NULL sau 9 atunci ← 10 ← + 1
![{\displaystyle key[x]<key[min[H]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/678e72a132e9ae0bbee03a96ad87372a80588594)
Costul amortizat al unei proceduri este egal cu costul real al acesteia .
Găsirea nodului minim
Procedura Fib_Heap_Minimum returnează un .
Costul amortizat al unei proceduri este egal cu costul real al acesteia .
Unirea a două grămezi Fibonacci
Fib_Heap_Union 1 ← Make_Fib_Heap() 2 ← 3 Adăugarea unei liste de rădăcini la o listă de rădăcini 4 dacă ( = NULL) sau ( ≠ NULL și < ) 5 apoi ← 6 ← 7 Eliberați obiectele și 8 reveniți
![{\displaystyle min[H_{1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c06be73dfdc2ebd7713d3a946a91127d751c86dd)
![{\displaystyle min[H_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e4c15d462e9bc769e328ba3b93711b75d21de68)
![{\tasta de stil de afișare[min[H_{2}]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd38f11d72e5ef38a1dba12f4131e25d75e72ccf)
![{\tasta de stil de afișare[min[H_{1}]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05f66202f4a1f1ef6be319ab0caa46a70aa702da)
![{\displaystyle n[H_{1}]+n[H_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e121253884bf636242ef97daaf19c6dffa47226e)
Costul amortizat al unei proceduri este egal cu costul real al acesteia .
Extragerea nodului minim
Fib_Heap_Extract_Min 1 ← 2 dacă ≠ NULL 3 apoi pentru fiecare copil al nodului 4 face Add to root list 5 ← NULL 6 Eliminați din lista rădăcină 7 dacă = 8 , atunci ← NULL 9 else ← 10 Consolidează 11 ← 12 returnează
![{\displaystyle dreapta[z]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef6c0ca5e045f05b51a8e85a71a2652179a28f23)
![{\displaystyle n[H]-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ed2c368ce89423e341bd76679b6a7a18e720e17)
La una dintre etapele operației de extragere a nodului minim se efectuează compactarea ( ing. consolidare ) a listei de rădăcini . Pentru a face acest lucru, utilizați procedura de ajutor Consolidate. Această procedură folosește o matrice auxiliară . Dacă , atunci este în prezent o rădăcină cu grad .
Consolidați 1 pentru ← 0 la 2 face ← NULL 3 pentru fiecare nod din lista rădăcină 4 face ← 5 ← 6 în timp ce ≠ NULL 7 face ← //Nod cu același grad ca 8 dacă 9 atunci schimbă ↔ 10 Fib_Heap_Link 11 ← NULL 12 ← 13 ← 14 ← NULL 15 pentru ← 0 până la 16 faceți dacă ≠ NULL 17 apoi Adăugați la lista rădăcină 18 dacă = NULL sau 19 apoi ← Fib_Heap_Link 1 Eliminați din lista rădăcină 2 Faceți un nod copil , incrementați 3 ← FALSE![{\displaystyle A[0..D[n[H]]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16a8aaf0c3fea41669e247dae3c99739997608c7)
![{\displaystyle A[i]=y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1773ac5c49b3da8c9e09a416b77c6fe80c7a307)
![{\displaystyle grad[y]=i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd44fdeab4b5b858a4e9e6d2c45ffcdcf96af6fc)
![{\displaystyle D(n[H])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6561060baee3b079d50a46f93444ab97506a9f5)
![{\displaystyle A[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a0d7a8a3371fad84f7032042e8d1e1caf6aa15e)
![{\displaystyle A[d]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/042feac7bdbe07a6252a95c7129cd511404b28ff)
![{\displaystyle key[x]>key[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07c4916c2e2b340131b0a221ca3590ecf2f98357)
![{\tasta de afișare[A[i]]<tasta[min[H]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3a421f33d981dab3125f64324a79d34de6ae8f4)
![{\displaystyle mark[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aecc871ae5dc12bfc3206f13c2a545fcd974bae4)
Costul amortizat al extragerii nodului minim este de .
Tasta descrescătoare
Fib_Heap_Decrease_Key 1 dacă 2 , atunci eroarea „Cheia nouă este mai mare decât cea actuală” 3 ← 4 ← 5 dacă ≠ NULL și 6 atunci Cut 7 Cascading_Cut 8 dacă 9 atunci ← Tăiați 1 Eliminați din lista nodurilor copil , reduceți 2 Adăugați la lista rădăcinilor 3 ← NULL 4 ← FALS Cascading_Cut 1 ← 2 dacă ≠ NULL 3 atunci dacă = FALS 4 apoi ← ADEVĂRAT 5 altfel Cut 6 Cascading_Cut
![{\displaystyle k>tasta[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce139201a27c8a99d5bc6e6b21ccff58421d5225)
![{\displaystyle key[x]<key[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b19c276ef004ee01d9243b7dae5ca4d3550d9b6)
![{\displaystyle grad[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a84c755349b58d4dbdf25eee53cabead167a765c)
![{\displaystyle p[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8c4860ad95bb383f9e80c71fb26ef7e3c706f92)
Costul amortizat al reducerii cheii nu depășește .
Ștergerea unui nod
Fib_Heap_Delete 1 Fib_Heap_Decrease_Key ∞ 2 Fib_Heap_Extract_Min
Timpul de derulare amortizat al procedurii este de .
Vezi și
Link -uri
- Implementarea structurii în C
- Vladimir Alekseev, Vladimir Talanov, Curs 7: Binomial and Fibonacci Heaps // „Data Structures and Computational Models”, 26.09.2006, intuit.ru
Literatură
- Thomas H. Kormen et al.Algoritmi : construcție și analiză. - Ed. a II-a. - M . : Editura Williams , 2007. - S. 1296. - ISBN 5-8459-0857-4 .
- Mehlhorn, Kurt, Sanders, Peter. 6.2.2 Fibonacci Heaps // Algoritmi și structuri de date: Cutia de instrumente de bază. - Springer, 2008. - 300 p. — ISBN 978-3-540-77978-0 .