Fibonacci-kasa
Fibonacci-kasa ( eng. Fibonacci-kasa ) on tietorakenne , joka on joukko puita , jotka on järjestetty ei-laskevan pyramidin ominaisuuden mukaisesti. Michael Fredman ja Robert Tarjan esittelivät Fibonacci-kasat vuonna 1984 .
Rakenne on " Priority Queue " -abstraktin tietotyypin toteutus , ja se on huomionarvoinen siinä mielessä, että toimintojen, jotka eivät vaadi poistamista, kuoletettu ajoaika on ( binäärikeon ja binomiaalisen keon jaksotettu ajoaika on ). Tavallisten operaatioiden , , lisäksi Fibonacci-keon avulla voit suorittaa kahden kasan yhdistämisen ajassa. INSERTMINDECREASE-KEYUNION
Rakenne
- Fibonacci-kasa on kokoelma puita .
- Jokainen puu on keon ominaisuuden alainen ( eng. min-heap property ): kunkin solmun avain ei ole pienempi kuin sen pääsolmun avain.
- Jokainen solmu sisältää seuraavat osoittimet ja kentät:
- - kenttä, johon avain on tallennettu;
- — osoitin pääsolmuun;
- — osoitin yhteen lapsisolmuista;
- - osoitin vasempaan sisarsolmuun;
- - osoitin oikeaan sisarsolmuun;
- - kenttä, joka tallentaa lapsisolmujen lukumäärän;
- on boolen arvo, joka osoittaa, onko solmu menettänyt lapsisolmuja sen jälkeen, kun siitä tuli jonkin toisen solmun lapsisolmu.
- Lapsisolmut yhdistetään osoittimien avulla yhdeksi sykliseksi kaksoislinkitetyksi lapsisolmuluetteloksi ( eng. child list ) .
- Kaikkien puiden juuret on yhdistetty osoittimien avulla ja sykliseksi kaksoislinkitetyksi juuriluetteloksi ( eng. root list ).
- Koko Fibonacci-kasalle tallennetaan myös osoitin solmuun, jossa on vähimmäisavain , joka on yhden puun juuri. Tätä solmua kutsutaan minimisolmuksi .
- Nykyinen solmujen määrä sijainnissa on tallennettu kohtaan .
![{\displaystyle key[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)
![{\näyttötyyli lapsi[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7983ae8a15176fca40c69829753ebff7acd09cd)
![{\displaystyle left[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fa7823fa23979d95eb14ab7667a573c22e01b7a)
![{\displaystyle right[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11d488d953d9ad638c15d2594ab597b5e653f15e)
![{\näyttötyylin tutkinto[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fbb4e65cbfec576877633e2ad6ceaaaae241696)
![{\näyttötyylimerkki[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/542b7e5368647a254202d3b202a71c2df4bf1954)
![{\näyttötyyli 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)
Toiminnot
Uuden Fibonacci-keon luominen
Make_Fib_Heap-proseduuri palauttaa fibonacci-keon objektin ja = NULL. Ei ole puita .
![{\displaystyle n[H]=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6755b0e87ac6248f20059f3300df0f6cb90f896)
Toimenpiteen jaksotettu hankintameno on yhtä suuri kuin sen todellinen hankintameno .
Solmun lisääminen
Fib_Heap_Insert 1 ← 0 2 ← NULL 3 ← NULL 4 ← 5 ← 6 ← EPÄTOSI 7 Liitä juuriluettelo, joka sisältää , juuriluetteloon 8 jos = NULL tai 9 sitten ← 10 ← + 1
![{\displaystyle key[x]<key[min[H]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/678e72a132e9ae0bbee03a96ad87372a80588594)
Toimenpiteen jaksotettu hankintameno on yhtä suuri kuin sen todellinen hankintameno .
Minimisolmun etsiminen
Fib_Heap_Minimum-proseduuri palauttaa .
Toimenpiteen jaksotettu hankintameno on yhtä suuri kuin sen todellinen hankintameno .
Kahden Fibonacci-kasan liitto
Fib_Heap_Union 1 ← Make_Fib_Heap() 2 ← 3 juuriluettelon lisääminen juuriluetteloon 4 jos ( = NULL) tai ( ≠ NULL ja < ) 5 sitten ← 6 ← 7 Vapauta objektit ja 8 palaa
![{\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)
![{\displaystyle key[min[H_{2}]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd38f11d72e5ef38a1dba12f4131e25d75e72ccf)
![{\displaystyle key[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)
Toimenpiteen jaksotettu hankintameno on yhtä suuri kuin sen todellinen hankintameno .
Vähimmäissolmun purkaminen
Fib_Heap_Extract_Min 1 ← 2 jos ≠ NULL 3 ja sitten jokaiselle solmun 4 alapuolelle tee Lisää juuriluetteloon 5 ← NULL 6 Poista juuriluettelosta 7 if = 8 sitten ← NULL 9 muuta ← 10 Yhdistä 11 ← 12 palautusta
![{\displaystyle right[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)
Yhdessä minimisolmun purkamisen vaiheista suoritetaan juuriluettelon tiivistäminen ( eng. consolidating ) . Voit tehdä tämän käyttämällä Consolidate Helper -menettelyä. Tämä menettely käyttää aputaulukkoa . Jos , niin on tällä hetkellä juuri ja aste .
Yhdistä 1 arvolle ← 0 - 2 do ← NULL 3 jokaiselle juuriluettelon solmulle 4 tee ← 5 ← 6 , kun taas ≠ NULL 7 tee ← //Solmu samalla asteella kuin 8 , jos 9 sitten vaihda ↔ 10 Fib_Heap_Link 11 ← NULL 12 ← 13 ← 14 ← NULL 15 ← 0 - 16 tee , jos ≠ NULL 17 sitten Lisää juuriluetteloon 18 if = NULL tai 19 sitten ← Fib_Heap_Link 1 Poista juuriluettelosta 2 Tee lapsisolmu , lisäys 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-aste[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)
![{\displaystyle key[A[i]]<avain[min[H]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3a421f33d981dab3125f64324a79d34de6ae8f4)
![{\näyttötyylimerkki[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aecc871ae5dc12bfc3206f13c2a545fcd974bae4)
Minimisolmun purkamisen jaksotettu hankintameno on .
Pienennysnäppäin
Fib_Heap_Decrease_Key 1 , jos 2 , niin virhe "Uusi avain on suurempi kuin nykyinen" 3 ← 4 ← 5 jos ≠ NULL ja 6 sitten Leikkaa 7 Cascading_Cut 8 jos 9 niin ← Leikkaa 1 Poista lapsisolmujen luettelosta , pienennä 2 Lisää juuriluetteloon 3 ← NULL 4 ← EPÄTOSI Cascading_Cut 1 ← 2 , jos ≠ NULL 3 sitten jos = EPÄTOSI 4 sitten ← TRUE 5 else Cut 6 Cascading_Cut
![{\displaystyle k>key[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)
![{\näyttötyylin tutkinto[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)
Avainvähennyksen jaksotettu hankintameno ei ylitä .
Solmun poistaminen
Fib_Heap_Delete 1 Fib_Heap_Decrease_Key ∞ 2 Fib_Heap_Extract_Min
Toimenpiteen jaksotettu ajoaika on .
Katso myös
Linkit
- Rakenteen toteutus C :ssä
- Vladimir Alekseev, Vladimir Talanov, Luento 7: Binomi- ja Fibonacci -kasat // "Datarakenteet ja laskennalliset mallit", 26.09.2006, intuit.ru
Kirjallisuus
- Thomas H. Kormen et al. Algoritmit: rakentaminen ja analyysi. - 2. painos - M . : Williams Publishing House , 2007. - S. 1296. - ISBN 5-8459-0857-4 .
- Mehlhorn, Kurt, Sanders, Peter. 6.2.2 Fibonacci-kekot // Algoritmit ja tietorakenteet: Perustyökalut. - Springer, 2008. - 300 s. — ISBN 978-3-540-77978-0 .