Kopiec Fibonacciego
W informatyce kopiec Fibonacciego to struktura danych realizująca operacje kolejki priorytetowej, składająca się z kolekcji drzew z porządkiem kopcowym. Kopce te mają lepszy czas zamortyzowany, niż wiele innych implementacji kolejek priorytetowych, w tym kopce binarne i dwumianowe. Michael L. Friedman i Robert E. Tarjan odkryli kopce Fibonacciego w 1984 roku i opublikowali ich opis w czasopiśmie naukowym w 1987 roku. Nazwali je kopcami Fibonacciego w nawiązaniu do liczb Fibonacciego, które są używane do ich analizy.
Dla kopców Fibonacciego operacja znalezienia minimum zajmuje czas stały (O(1)) w sensie zamortyzowanym.[1] podobnie jak operacje wstawiania oraz zmniejszania klucza.[2] Usuwanie elementu (najczęściej jest używany w specjalnym przypadku usuwania minimalnego elementu) działa w czasie zamortyzowanym O(log n), gdzie n to rozmiar stosu.[2] Oznacza to, że zaczynając od pustej struktury, dowolny ciąg a operacji wstawiania oraz zmniejszania kluczy i b operacji usunięć zajmie O(a + b log n) czasu (najgorszy przypadek), gdzie n to maksymalny rozmiar kopca. Taki sam ciąg operacji w kopcu dwumianowym miałby złożoność O((a+b) log n). Możliwa jest także operacja łączenia dwóch kopców Fibonacciego w stałym czasie (zamortyzowanym).
Implementacja kolejki priorytetowej w oparciu o kopce Fibonacciego poprawia złożoność wielu ważnych algorytmów, takich jak algorytm Dijkstry do obliczania najkrótszej ścieżki między dwoma węzłami grafu.
Struktura[edytuj | edytuj kod]
Kopiec Fibonacciego jest kolekcją drzew, które spełniają wymogi kopca, czyli klucz dziecka jest zawsze większy lub równy kluczowi rodzica. Oznacza to, że minimalny klucz zawsze jest korzeniem jednego z drzew. W porównaniu do kopców dwumianowych, struktura ta jest jednak bardziej elastyczna, ponieważ drzewa nie muszą być w kolejności posortowanej, dodatkowo nie ma restrykcyjnych wymagań co do rzędów poszczególnych drzew. Ta elastyczność pozwala na leniwe wykonywanie niektórych czynności, odkładając część pracy na poczet następnych operacji. Na przykład łączenie dwóch kopców odbywa się poprzez proste złączenie obu list drzew.
Jednak w pewnym momencie, jakiś porządek musi być wprowadzony do kopca w celu osiągnięcia pożądanego czasu. W szczególności, stopnie węzłów (tutaj stopień oznacza liczbę dzieci) są dość niskie: każdy węzeł ma stopień nie większy niż O(log n) i rozmiar poddrzewa zakorzenionego w węźle stopnia k jest co najmniej Fk+2, gdzie Fk jest k-tą liczbą Fibonacciego. Jest to możliwe dzięki temu, że możemy odcinać tylko jedno dziecko każdemu z wierzchołków. Przy próbie odcięcia drugiego dziecka (wierzchołkowi, który stracił już jedno dziecko), powinniśmy odciąć również ten wierzchołek i stworzyć nowe drzewo z nim jako korzeniem. Natomiast podczas operacji usuwania minimum, liczba drzew jest zmniejszana.
Realizacja operacji[edytuj | edytuj kod]
Aby zapewnić szybkie usuwanie i łączenie, korzenie wszystkich drzew są ze sobą powiązane za pomocą cyklicznej podwójnie wiązanej listy. Dzieci każdego węzła także są związane za pomocą takiej listy. Ponadto, zapamiętujemy sobie wskaźnik na korzeń, który zawiera minimalny klucz.
Operacja znajdowania minimum jest teraz trywialna, ponieważ ciągle pamiętamy wskaźnik na minimalny element. Warto zauważyć, że operacja ta nie modyfikuje nam kopca.
Jak wspomniano powyżej, łączenie kopców odbywa się poprzez łączenie list korzeni obu kopców w związku z tym jest to operacja wykonywana w czasie stałym.
Operacja wstawiania polega na stworzeniu nowego kopca z jednym elementem i połączeniu go z resztą.
Operacja usunięcia minimum przebiega w 3 fazach. Po pierwsze, usuwamy korzeń zawierający minimalny element, a jego dzieci (z poddrzewami) dołączamy do listy drzew kopca. Operacja ta jest kosztu liniowego względem liczby dzieci wierzchołka o minimalnym kluczu, jednak w ujęciu zamortyzowanym faza ta zajmuje O(log n).
Jednak, aby zakończyć usuwanie minimalnego wierzchołka musimy uaktualnić wskaźnik na minimalny klucz. Niestety na liście korzeni może być n elementów, które musimy przejrzeć, jednakże podczas drugiej fazy łączymy ze sobą drzewa o takich samych stopniach (stopień drzewa wyraża się stopniem korzenia tego drzewa). Łączenie drzew polega na podłączeniu wierzchołka o większym kluczu jako dziecko korzenia drugiego drzewa. W ten sposób korzeniem pozostaje najmniejszy wierzchołek. Aby efektywnie wyszukiwać drzewa o tym samym stopniu tworzymy tablicę wskaźników o długości O(log n) gdzie trzymamy wskaźniki do drzew o kolejnych rzędach. Jeśli rozpatrujemy drzewo o rzędzie k, ale w k-tej komórce tablicy istnieje już wskaźnik, oznacza to ze powinniśmy złączyć oba drzewa i zapisać w komórce k+1. Aktualny koszt wynosi O(n +m), gdzie m jest liczbą korzeni na początku drugiej fazy algorytmu. Finalnie otrzymujemy nie więcej niż O(log n) korzeni o różnych stopniach.
Podczas trzeciego etapu przeglądamy korzenie drzew w celu znalezienia minimum, co zajmuje O(log n). Łączny zamortyzowany koszt wynosi więc O(log n).
Operacje zmniejszenia klucza zaczyna od zmniejszenia wartości zadanego wierzchołka i w razie gdy nowa wartość zaburza porządek kopcowy (czyli wierzchołek jest mniejszy niż rodzic) wywołujemy operacje odcinania rozważanego wierzchołka.
Operacja odcinania wierzchołka x odcina go od jego ojca (y) i dołącza do listy korzeni kopca. Dodatkowo y zostaje oznaczony jako wierzchołek, który utracił jedno dziecko. Przy próbie odcięcia drugiego dziecka, nie odcinamy go, tylko wywołujemy cut(y), przenosząc operację w górę drzewa tak długo, aż dojdziemy do korzenia, lub wierzchołka który nie utracił jeszcze syna.
Przypisy[edytuj | edytuj kod]
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990].
- ↑ a b Fredman, Michael Lawrence; Tarjan, Robert E. (1987).