Ta odpowiedź będzie dość długa, ale mam nadzieję, że pomoże w zrozumieniu, skąd pochodzi sterta Fibonacciego. Zakładam, że znasz już hałdy dwumianowe i analizy amortyzacyjne .

Motywacja: Dlaczego Fibonacciego?

Przed skokiem do stosów Fibonacciego, prawdopodobnie dobrze jest zbadać, dlaczego w ogóle ich potrzebujemy. Istnieje wiele innych typów stosów (stosy binarne i binomial heaps, na przykład), więc po co nam kolejny?

Główny powód pojawia się w algorytmie Dijkstry i algorytmie Prima. Oba te algorytmy graficzne działają poprzez utrzymywanie kolejki priorytetów przechowującej węzły z powiązanymi priorytetami. Co ciekawe, algorytmy te opierają się na operacji sterty o nazwie decreate-key, która pobiera wpis już w kolejce priorytetów ,a następnie zmniejsza jego klucz (tzn. zwiększa jego priorytet). W rzeczywistości, wiele czasu trwania z tych algorytmów jest wyjaśnione przez liczbę razy trzeba wywołać decrease-key. Gdybyśmy mogli zbudować strukturę danych, która zoptymalizowałaby klucz redukcji, moglibyśmy zoptymalizować wydajność tych algorytmów. W przypadku sterty binarnej i sterty dwumianowej, klawisz decrease-key zajmuje czas O (log n), gdzie n jest liczbą węzłów w kolejce priorytetów. Jeśli moglibyśmy Upuścić to do O(1), to złożoności czasowe algorytmu Dijkstry i algorytmu Prim spadłyby Z O(M log n) do (m + n log n), które jest asymptotycznie szybszy niż wcześniej. Dlatego warto spróbować zbudować strukturę danych, która skutecznie obsługuje decrease-key.

Jest jeszcze jeden powód, aby rozważyć zaprojektowanie lepszej struktury sterty. Podczas dodawania elementów do pustej sterty binarnej, każde wstawianie zajmuje czas O (log n). Możliwe jest zbudowanie sterty binarnej w czasie O (N) jeśli znamy wszystkie N elementów z góry, ale jeśli elementy docierają do strumienia, nie jest to możliwe. W przypadku stosu dwumianowego, wstawianie n kolejnych elementów zajmuje czas o (1) każdy, ale jeśli wstawki są przeplatane delecjami, wstawki mogą skończyć się pobieraniem czasu Ω (log n) każdy. Dlatego możemy chcieć wyszukać implementację kolejki priorytetów, która optymalizuje wstawki tak, aby każda z nich zajmowała O(1) więcej czasu.

Krok Pierwszy: Leniwe Hałdy Dwumianowe

Aby rozpocząć budowanie stosu Fibonacciego, zaczniemy od stosu dwumianowego i zmodyfikujemy go, starając się, aby wstawianie zajęło czas O (1). To nie wszystko nierozsądne jest wypróbowanie tego - w końcu, jeśli mamy robić dużo wejść, a nie tyle dequeues, to optymalizacja wejść ma sens.

Jeśli pamiętasz, stosy dwumianowe działają, przechowując wszystkie elementy w stosie w zbiorze drzew dwumianowych. Drzewo dwumianowe rzędu n ma w sobie 2^N węzły, A sterta jest strukturą jako zbiór drzew dwumianowych, które wszystkie są zgodne z właściwością sterty. Zazwyczaj algorytm wstawiania w stosie dwumianowym działa jak następuje:

• Utwórz nowy węzeł singleton (jest to drzewo rzędu 0).
• jeśli istnieje drzewo rzędu 0:
  • połącz dwa drzewa rzędu 0 w drzewo rzędu 1.
  • jeśli istnieje drzewo rzędu 1:
    • połącz dwa drzewa rzędu 1 Razem w drzewo rzędu 2.
    • jeśli istnieje drzewo rzędu 2:
    • ...

Ten proces zapewnia, że w każdym momencie w czasie, jest co najwyżej jedno drzewo każdego rzędu. Ponieważ każde drzewo posiada wykładniczo więcej węzłów niż jego kolejność, gwarantuje to, że całkowita liczba drzew jest mała, co pozwala dequeues działać szybko(ponieważ nie musimy patrzeć na zbyt wiele różnych drzew po wykonaniu kroku dequeue-min).

Oznacza to jednak również, że najgorszym czasem wstawiania węzła do stosu dwumianowego jest Θ(log n), ponieważ możemy mieć Θ (log n) drzewa, które muszą zostać połączone razem. Te drzewa muszą być połączone ze sobą tylko dlatego, że musimy utrzymać niską liczbę drzew podczas wykonywania kroku dequeue, a w przyszłych wstawkach nie ma absolutnie żadnej korzyści z utrzymania niskiej liczby drzew.

To wprowadza pierwsze odejście od stosów dwumianowych:

Modyfikacja 1: podczas wstawiania węzła do sterty, wystarczy utworzyć drzewo rzędu 0 i dodać je do istniejącej kolekcji drzew. Nie konsoliduj drzew razem.

Jest jeszcze jedna zmiana, którą możemy wprowadzić. Zwykle, gdy łączymy ze sobą dwie stosy dwumianowe, wykonujemy krok scalania, aby połączyć je ze sobą w sposób zapewniający, że w wynikowym drzewie znajduje się co najwyżej jedno drzewo każdego rzędu. Ponownie robimy tę kompresję, aby dequeues były szybkie i nie ma prawdziwego powodu, dla którego operacja scalania powinna za to płacić. Dlatego dokonamy drugiej zmiany:

Modyfikacja 2: podczas łączenia dwóch stosów razem, po prostu połącz wszystkie ich drzewa razem bez robienia / align = "left" / Nie konsolidować żadnych drzew razem.

Jeśli wprowadzimy tę zmianę, dość łatwo uzyskamy o(1) performace na naszych operacjach enqueue, ponieważ wszystko, co robimy, to tworzenie nowego węzła i dodawanie go do kolekcji drzew. Jeśli jednak dokonamy tej zmiany i nie zrobimy nic innego, całkowicie przerwiemy działanie operacji dequeue-min. Przypomnijmy, że dequeue-min musi skanować korzenie wszystkich drzew w stercie po usunięciu minimalnej wartości, aby że może znaleźć najmniejszą wartość. Jeśli dodamy Θ(n) węzły wstawiając je w sposób, nasza operacja dequeue będzie musiała spędzić czas Θ (n) przeglądając wszystkie te drzewa. To wielki hit... możemy tego uniknąć?

Jeśli nasze wstawki naprawdę dodają więcej drzew, to pierwsza dequeue, którą zrobimy, z pewnością zajmie Ω (n) czas. Nie oznacza to jednak, że każda dequeue musi być droga. Co się stanie, jeśli po zrobieniu dequeue połączymy wszystkie drzewa w stos razem tak, że kończymy tylko z jednym drzewem każdego rzędu? Początkowo zajmie to dużo czasu, ale jeśli zaczniemy robić kilka dekeui po kolei, te przyszłe dekeui będą znacznie szybsze, ponieważ wokół jest mniej drzew.

Jest jednak mały problem z tą konfiguracją. W normalnym stosie dwumianowym drzewa są zawsze przechowywane w porządku. Jeśli tylko będziemy wrzucać nowe drzewa do naszej kolekcji drzew, łączymy je w losowych momentach i dodajemy nawet więcej drzew po tym, nie ma gwarancji, że drzewa będą w jakiejkolwiek kolejności. Dlatego będziemy potrzebować nowego algorytmu, aby połączyć te drzewa razem.

Intuicja stojąca za tym algorytmem jest następująca. Załóżmy, że tworzymy tabelę hash, która mapuje od kolejności drzew do drzew. Możemy wtedy wykonać następującą operację dla każdego drzewa w strukturze danych:

• Spójrz w górę i zobacz, czy jest już drzewo tej kolejności.
• jeśli nie, Wstaw bieżące drzewo do stół hash.
• inaczej:
  • Połącz obecne drzewo z drzewem tego rzędu, usuwając stare drzewo z stół hash.
  • rekurencyjnie powtórz ten proces.

Ta operacja zapewnia, że kiedy skończymy, będzie co najwyżej jedno drzewo każdego rzędu. Jest również stosunkowo wydajny. Załóżmy, że zaczynamy od T drzewa ogółem, a kończymy na t drzewa ogółem. Liczba łącznych połączeń, które zakończymy będzie T - T-1, i za każdym razem robimy scalanie zajmie trochę czasu O (1), aby to zrobić. Dlatego runtime dla tej operacji będzie liniowy w liczbie drzew (każde drzewo jest odwiedzane przynajmniej raz) plus liczba wykonanych mergów.

Jeśli liczba drzew jest mała (powiedzmy Θ (log n)), to operacja ta zajmie tylko czas O (log n). Jeśli liczba drzew jest duża (powiedzmy Θ(n)), operacja ta zajmie Θ(n) czas, ale pozostawi tylko Θ (log n) drzewa pozostały, dzięki czemu przyszłe dequeues znacznie szybciej.

Możemy określić tylko o ile lepsze rzeczy uzyskają wykonując zamortyzowaną analizę i wykorzystując potencjalną funkcję. Niech Φ będzie naszą funkcją potencjalną i niech Φ będzie liczbą drzew w strukturze danych. Oznacza to, że koszty operacji są następujące:

• Insert : czy O(1) działa i zwiększa potencjał o jeden. Koszt amortyzowany wynosi O (1).
• Merge : czy O(1) działa. Potencjał jednej sterty spada do 0, a potencjał drugiej sterty zwiększa się o odpowiedniej kwoty, więc nie ma zmiany potencjału netto. Amortyzowany koszt wynosi zatem O (1).
• Dequeue-Min : czy O(#trees + #merges) działa i zmniejsza potencjał do Θ(log n), liczby drzew, które mielibyśmy w drzewie dwumianowym, gdybyśmy chętnie łączyli drzewa razem. Możemy to wyjaśnić w inny sposób. Niech liczba drzew będzie zapisana jako Θ (log n) + E, gdzie E jest "nadmiarem" liczby drzew. W takim przypadku całkowita wykonana praca jest Θ(log n + E + #merges). Zauważ, że zrobimy jedno scalenie na nadmiarowe drzewo, a więc całkowita wykonana praca to Θ (log n + E). Ponieważ nasz potencjał spada liczbę drzew z Θ (log n) + E do Θ (log n), spadek potencjału wynosi -E. zatem zamortyzowany koszt dequeue-min wynosi Θ (log n).

Innym intuicyjnym sposobem, aby zobaczyć, dlaczego zamortyzowany koszt dequeue-min jest Θ (log n), jest spojrzenie na dlaczego mamy nadwyżki drzew. Te dodatkowe drzewa są tam, bo te darned chciwe wstawki robisz te wszystkie dodatkowe drzewa i nie płacisz za nie! Możemy zatem "backcharge" koszt związany z wykonaniem wszystkich połączeń z powrotem do poszczególnych wstawek, które zajmowały cały ten czas, pozostawiając za sobą operację Θ (log n) "rdzeń" i kilka innych operacji, które będziemy winić na wstawkach.

Dlatego:

Modyfikacja 3: podczas operacji dequeue-min należy skonsolidować wszystkie drzewa, aby mieć pewność, że jest co najwyżej jedno drzewo z każdego spokój.

W tym momencie mamy insert i merge działające w czasie O(1) i dequeues działające w czasie amortyzowanym O (log n). To całkiem sprytne! Jednak nadal nie mamy jeszcze działającego klucza obniżania. To będzie najtrudniejsza część.

Krok Drugi: Implementacja Klucza Zmniejszania

W tej chwili mamy "leniwe dwumianowe stosy" zamiast stosu Fibonacciego. Prawdziwa zmiana pomiędzy dwumianową kupą a kupą Fibonacciego polega na tym, jak zaimplementujemy klucz spadku.

Przypomnienie że operacja decreate-key powinna przyjmować wpis już w stercie (Zwykle mielibyśmy do niego wskaźnik) i nowy priorytet, który jest niższy od istniejącego priorytetu. Następnie zmienia priorytet tego elementu na nowy, niższy priorytet.

Możemy zaimplementować tę operację bardzo szybko (w czasie O (log n)) za pomocą prostego algorytmu. Weźmy element, którego klucz powinien być zmniejszony (który może znajdować się w czasie O(1); pamiętajmy, że zakładamy, że mamy do niego wskaźnik) i niżej to priorytet. Następnie wielokrotnie wymieniaj go z węzłem macierzystym, o ile jego priorytet jest niższy niż jego rodzic, zatrzymując się, gdy węzeł spocznie lub gdy dotrze do korzenia drzewa. Operacja ta zajmuje czas O(log n), ponieważ każde drzewo ma wysokość co najwyżej O(log n), A każde porównanie zajmuje czas O (1).

Pamiętaj jednak, że staramy się zrobić jeszcze lepiej niż to - chcemy, aby runtime było O(1)! To jest bardzo trudne do dopasowania. Nie możemy użyć żadnego procesu, który przesunie węzeł w górę lub w dół drzewa, ponieważ drzewa te mają wysokość, która może być Ω (log n). Musimy spróbować czegoś bardziej drastycznego.

Załóżmy, że chcemy zmniejszyć klucz węzła. Właściwość heap zostanie naruszona tylko wtedy, gdy nowy priorytet węzła jest niższy niż priorytet jego rodzica. Jeśli spojrzymy na poddrzewo zakorzenione w tym konkretnym węźle, nadal będzie ono posłuszne właściwości sterty. Więc oto całkowicie szalony pomysł: co jeśli ilekroć zmniejszamy klucz węzła, tniemy link do węzła nadrzędnego, a następnie doprowadzić cały podtree zakorzenione w węźle z powrotem do najwyższego poziomu drzewa?

Modification 4: Have decrease-key zmniejsza klucz węzła i, jeśli jego priorytet jest mniejszy niż priorytet rodzica, wytnij go i dodaj do listy głównej.

Jaki będzie efekt tej operacji? Wydarzy się kilka rzeczy.

1. węzeł, który wcześniej miał nasz węzeł jako dziecko, teraz myśli, że ma zły numer dzieci. Przypomnijmy, że drzewo dwumianowe rzędu n jest zdefiniowane jako N dzieci, ale to już nie jest prawdą.
2. zbiór drzew na liście korzeniowej wzrośnie, zwiększając koszty przyszłych operacji dequeue.
Drzewa w naszej stercie niekoniecznie będą już drzewami dwumianowymi. Mogą to być" dawniej " drzewa dwumianowe, które traciły dzieci w różnych momentach w czasie.

Liczba (1) nie stanowi większego problemu. Jeśli wytniemy węzeł z jego rodzica, możemy po prostu zmniejszyć kolejność tego węzła o jeden, aby wskazać, że ma mniej dzieci, niż wcześniej sądził. Liczba (2) również nie stanowi problemu. Możemy po prostu cofnąć dodatkową pracę wykonaną w następnej operacji dequeue-min do operacji zmniejszania klucza.

Liczba (3) jest bardzo, bardzo poważnym problemem, który musimy rozwiązać. Problem polega na tym, że wydajność stosu dwumianowego częściowo wynika z faktu, że każdy zbiór węzłów n może być przechowywany w zbiorze Θ (log n) drzewa różnej kolejności. Powodem tego jest to, że każde drzewo dwumianowe ma w sobie 2 ^N węzłów. Jeśli możemy zacząć wycinać węzły z drzew, to ryzykujemy, że drzewa mają dużą liczbę dzieci (czyli wysoką kolejność), ale nie mają wielu węzłów w sobie. Na przykład, załóżmy, że zaczynamy od pojedynczego drzewa rzędu k, a następnie wykonujemy operacje z kluczem spadku na wszystkich wnękach K. To pozostawia k jako drzewo z rzędu k, ale które zawiera tylko K + 1 węzłów całkowitych. Jeśli będziemy powtarzać ten proces wszędzie, może skończyć się kilka drzew różnych rzędów, które mają bardzo małą liczbę dzieci w nich. W związku z tym, kiedy wykonujemy naszą operację łączenia, aby zgrupować drzewa razem, możemy nie zmniejszyć liczby drzew do możliwego do opanowania poziomu, łamiąc Θ(log n)-czas związany, którego tak naprawdę nie chcemy stracić.

W tym momencie, mamy mały problem. Musimy mieć dużą elastyczność w tym, jak drzewa mogą być przekształcane tak, że my możemy uzyskać funkcjonalność o(1) time decrease-key, ale nie możemy pozwolić, aby drzewa zostały przekształcone arbitralnie lub skończymy z amortyzowanym uruchomieniem decrease-key zwiększającym się do czegoś większego niż o (log n).

Potrzebny wgląd - i, szczerze mówiąc, to, co uważam za prawdziwy geniusz w stercie Fibonacciego - jest kompromisem między tymi dwoma. Idea jest następująca. Jeśli wytniemy drzewo z jego rodzica, już planujemy zmniejszenie rangi węzła nadrzędnego o jeden. Problem tak naprawdę powstaje, gdy węzeł traci dużo dzieci, w którym to przypadku jego ranga znacznie spada, nie wiedząc o tym żadne węzły wyżej w drzewie. Dlatego powiemy, że każdy węzeł może stracić tylko jedno dziecko. Jeśli węzeł straci drugie dziecko, odetniemy go od jego rodzica, co rozniesie informację, że brakuje węzłów wyżej w drzewie.

Okazuje się, że to świetny kompromis. Pozwala nam to na szybkie skrócenie klawiszy w większości konteksty (o ile węzły nie są potomkami tego samego drzewa) i tylko rzadko musimy "propagować" klucz zmniejszania poprzez wycinanie węzła od jego rodzica, a następnie wycinanie tego węzła od jego dziadków.

Aby śledzić, które węzły straciły dzieci, przypisujemy bit "mark" do każdego węzła. Każdy węzeł będzie początkowo miał bit znacznika wyczyszczony, ale gdy straci potomka, będzie miał ustawiony bit. Jeśli straci drugie dziecko po ustawieniu bitu, wyczyścimy ten bit, następnie odetnij węzeł od jego rodzica.

Modyfikacja 5 : przypisanie bitu znacznika do każdego węzła, który jest początkowo fałszywy. Gdy dziecko jest odcięte od nieoznaczonego rodzica, zaznacz go. Gdy dziecko zostanie odcięte od zaznaczonego rodzica, odznacz go i wytnij rodzica od jego rodzica.

In to starsze pytanie o przepełnienie stosu, naszkicowałem dowód, który pokazuje, że jeśli drzewa mogą być modyfikowane w ten sposób, to każde drzewo rzędu n musi zawiera co najmniej Θ (φⁿ) węzły, gdzie φ to złoty stosunek , około 1,61. Oznacza to, że liczba węzłów w każdym drzewie jest nadal wykładnicza w kolejności drzewa, choć jest to niższy wykładnik od poprzedniego. W rezultacie, przeprowadzona wcześniej analiza złożoności czasowej operacji klucza spadkowego nadal utrzymuje się, choć termin ukryty w Bitie Θ (log n) będzie inny.

Jest jeszcze jedna rzecz do rozważenia - co ze złożonością / align = "left" / Wcześniej było to O(1), ponieważ po prostu wycięliśmy drzewo zakorzenione w odpowiednim węźle i przenieśliśmy je do listy korzeni. Jednak teraz możemy wykonać "cięcie kaskadowe", w którym wycinamy węzeł z jego rodzica, a następnie wycinamy ten węzeł z jego rodzica, itp. Jak to daje o (1) klucze skrótu czasu?

Spostrzeżenie tutaj jest takie, że możemy dodać "charge" do każdej operacji klucza zmniejszania, którą możemy następnie wydać, aby odciąć węzeł rodzica od jego rodzica. Od kiedy my Wytnij węzeł od rodzica tylko wtedy, gdy stracił już dwoje dzieci, możemy udawać, że każda operacja zmniejszania klucza płaci za pracę niezbędną do wycięcia jego węzła nadrzędnego. Kiedy dokonamy cięcia rodzica, możemy obciąć koszt tego z powrotem do jednej z wcześniejszych operacji zmniejszenia klucza. W związku z tym, nawet jeśli każda indywidualna operacja klawisza zmniejszania może zająć dużo czasu, zawsze możemy amortyzować pracę we wcześniejszych wywołaniach, tak że czas wykonania jest amortyzowany O(1).

Krok Trzeci: Połączone Listy Obfitują!

Jest jeszcze jeden szczegół, o którym musimy porozmawiać. Struktura danych, którą opisałem do tej pory, jest trudna, ale nie wydaje się katastrofalnie skomplikowana. Stosy Fibonacciego mają reputację budzącego grozę... dlaczego?

Powodem jest to, że aby zaimplementować wszystkie opisane powyżej operacje, struktury drzewiaste muszą być zaimplementowane w bardzo sprytny sposób.

Zazwyczaj reprezentujesz drzewo wielowarstwowe, mając każdy punkt nadrzędny do wszystkich dzieci (być może przez posiadanie tablicy dzieci) lub przez używając reprezentacji left-child/right-sibling , gdzie rodzic ma wskaźnik do jednego dziecka, który z kolei wskazuje na listę pozostałych dzieci. Dla dwumianu, to jest idealne. Główną operacją, którą musimy wykonać na drzewach, jest operacja łączenia, w której jeden węzeł korzeniowy staje się dzieckiem drugiego, więc jest to całkowicie rozsądne dla wskaźników w drzewie skierowanych od rodziców do dzieci.

The problem w stercie Fibonacciego polega na tym, że reprezentacja ta jest nieefektywna, gdy rozważa się krok kluczowy spadku. Stosy Fibonacciego muszą obsługiwać wszystkie podstawowe manipulacje wskaźnikami standardowego stosu dwumianowego i zdolność wycinania pojedynczego dziecka od rodzica.

Rozważmy standardowe reprezentacje drzew wielowarstwowych. Jeśli reprezentujemy drzewo przez to, że każdy węzeł nadrzędny przechowuje tablicę lub listę wskaźników do jego potomków, to nie możemy efektywnie (w o(1)) usunąć potomka węzeł z listy dzieci. Innymi słowy, runtime dla decrease-key będzie zdominowany przez etap księgowania usuwania potomka, a nie logiczny krok przenoszenia poddrzewa do listy głównej! Ten sam problem pojawia się w reprezentacji lewe-dziecko, prawe-rodzeństwo.

Rozwiązaniem tego problemu jest przechowywanie drzewa w dziwaczny sposób. Każdy węzeł nadrzędny przechowuje wskaźnik do jednego (i dowolnego) jednego z jego dzieci. Dzieci są następnie przechowywane w kolistym listy, a każdy z nich wskazuje na rodzica. Ponieważ możliwe jest łączenie dwóch list połączonych cyklicznie w czasie O(1) i wstawianie lub usuwanie pojedynczego wpisu z jednego w czasie O(1), umożliwia to efektywne wsparcie niezbędnych operacji na drzewie:

• Uczyń jedno drzewo potomkiem drugiego: jeśli pierwsze drzewo nie ma dzieci, ustaw jego wskaźnik potomka, aby wskazywał na drugie drzewo. W przeciwnym razie, połącz drugie drzewo z kołowo połączoną listą Potomków pierwszego drzewo.

• Usuń węzeł potomny z drzewa: połącz ten węzeł potomny z połączonej listy dzieci dla węzła nadrzędnego. Jeśli jest to pojedynczy węzeł wybrany do reprezentowania dzieci węzła nadrzędnego, wybierz jeden z węzłów rodzeństwa, aby go zastąpić (lub ustaw wskaźnik na null, jeśli jest to ostatni węzeł potomny.)

Istnieje absurdalnie wiele przypadków do rozważenia i sprawdzenia podczas wykonywania wszystkich tych operacji po prostu ze względu na liczbę różnych przypadków krawędzi, które mogą się pojawić. Na napowietrzność związana ze wszystkimi wskaźnikami jest jednym z powodów, dla których stosy Fibonacciego są w praktyce wolniejsze niż sugerowałaby ich asymptotyczna złożoność (drugim dużym jest logika usuwania wartości minimalnej, która wymaga pomocniczej struktury danych).

Modification 6 : użyj niestandardowej reprezentacji drzewa, która wspiera efektywne łączenie drzew i wycinanie jednego drzewa z drugiego.

Podsumowanie

Mam nadzieję, że ta odpowiedź rzuca trochę światła na tajemnicę, jaką jest sterta Fibonacciego. Mam nadzieję, że możesz zobaczyć logiczny postęp od prostszej struktury (stosu dwumianowego) do bardziej złożonej struktury przez szereg prostych kroków opartych na rozsądnych spostrzeżeniach. Nie jest nierozsądne, aby wstawianie było skuteczne kosztem usuwania, a także nie jest zbyt szalone, aby zaimplementować klucz zmniejszania poprzez wycinanie podtypów. Stamtąd reszta szczegółów jest w zapewnieniu, że struktura jest wciąż wydajne, ale są bardziej konsekwencjami innych części, niż przyczynami.

Jeśli chcesz dowiedzieć się więcej o stosach Fibonacciego, możesz zapoznać się z tą dwuczęściową serią slajdów wykładowych. część pierwsza wprowadza hałdy dwumianowe i pokazuje, jak działają leniwe hałdy dwumianowe. część druga bada stosy Fibonacciego. Te slajdy są bardziej matematyczne niż to, o czym tutaj wspomniałem.

Mam nadzieję, że to pomoże!