Fibonacci Heap

W tym samouczku dowiesz się, czym jest sterta Fibonacciego. Znajdziesz również działające przykłady różnych operacji na stercie Fibonacciego w językach C, C ++, Java i Python.

Sterta Fibonacciego jest zmodyfikowaną postacią sterty dwumianowej z bardziej wydajnymi operacjami na sterty niż ta obsługiwana przez sterty dwumianowe i binarne.

W przeciwieństwie do sterty binarnej węzeł może mieć więcej niż dwoje dzieci.

Sterta Fibonacciego nazywana jest stertą Fibonacciego, ponieważ drzewa są tak skonstruowane, że drzewo rzędu n ma przynajmniej Fn+2węzły, gdzie Fn+2jest (n + 2)ndliczba Fibonacciego.

Fibonacci Heap

Właściwości stosu Fibonacciego

Ważnymi właściwościami sterty Fibonacciego są:

  1. Jest to zestaw drzew uporządkowanych w minimalny stos . (tj. rodzic jest zawsze mniejszy od dzieci).
  2. Wskaźnik jest utrzymywany na minimalnym węźle elementu.
  3. Składa się z zestawu zaznaczonych węzłów. (Zmniejsz działanie klawisza)
  4. Drzewa w stosie Fibonacciego są nieuporządkowane, ale mają korzenie.

Reprezentacja pamięci węzłów w stercie Fibonacciego

Korzenie wszystkich drzew są ze sobą połączone, co zapewnia szybszy dostęp. Węzły potomne węzła macierzystego są połączone ze sobą za pomocą okrągłej, podwójnie połączonej listy, jak pokazano poniżej.

Istnieją dwie główne zalety używania okrągłej listy podwójnie połączonej.

  1. Usunięcie węzła z drzewa wymaga O(1)czasu.
  2. Łączenie dwóch takich list wymaga O(1)czasu.
Struktura sterty Fibonacciego

Operacje na stercie Fibonacciego

Wprowadzenie

Algorytm

 insert (H, x) degree (x) = 0 p (x) = NIL child (x) = NIL left (x) = x right (x) = x mark (x) = FALSE konkatenuje listę główną zawierającą x z rootem list H if min (H) == NIL lub key (x) <key (min (H)) następnie min (H) = xn (H) = n (H) + 1

Wstawianie węzła do już istniejącej sterty następuje według poniższych kroków.

  1. Utwórz nowy węzeł dla elementu.
  2. Sprawdź, czy sterta jest pusta.
  3. Jeśli sterta jest pusta, ustaw nowy węzeł jako węzeł główny i oznacz go jako min.
  4. W przeciwnym razie wstaw węzeł do listy głównej i zaktualizuj min.
Przykład wstawienia

Znajdź min

Minimalny element jest zawsze podawany przez wskaźnik min.

Unia

Połączenie dwóch hałd Fibonacciego składa się z następujących kroków.

  1. Połącz korzenie obu stert.
  2. Zaktualizuj min, wybierając minimalny klucz z nowych list głównych.
Połączenie dwóch stosów

Wyodrębnij min

Jest to najważniejsza operacja na stercie fibonacciego. W tej operacji węzeł z minimalną wartością jest usuwany ze sterty, a drzewo jest ponownie dostosowywane.

Następujące kroki są wykonywane:

  1. Usuń węzeł min.
  2. Ustaw min-wskaźnik na następny root na liście głównej.
  3. Utwórz tablicę o rozmiarze równym maksymalnemu stopniowi drzew w stercie przed usunięciem.
  4. Wykonaj następujące czynności (kroki 5-7), aż nie będzie wielu korzeni o tym samym stopniu.
  5. Zamapuj stopień bieżącego pierwiastka (wskaźnik min) do stopnia w tablicy.
  6. Odwzoruj stopień następnego pierwiastka na stopień w tablicy.
  7. Jeśli istnieje więcej niż dwa odwzorowania dla tego samego stopnia, zastosuj operację unii do tych korzeni, tak aby zachowana została właściwość min-sterta (tj. Minimum znajduje się w katalogu głównym).

Realizację powyższych kroków można zrozumieć na poniższym przykładzie.

  1. Wykonamy operację extract-min na stercie poniżej. Fibonacci Heap
  2. Usuń węzeł min, dodaj wszystkie jego węzły podrzędne do listy głównej i ustaw wskaźnik min na następny węzeł główny na liście głównej. Usuń węzeł min
  3. Maksymalny stopień w drzewie to 3. Utwórz tablicę o rozmiarze 4 i odwzoruj stopień kolejnych pierwiastków za pomocą tablicy. Utwórz tablicę
  4. Tutaj 23 i 7 mają te same stopnie, więc połącz je. Zjednoczcie tych, którzy mają te same stopnie naukowe
  5. Ponownie, 7 i 17 mają te same stopnie, więc połącz je również. Zjednoczcie tych, którzy mają te same stopnie naukowe
  6. Ponownie 7 i 24 mają ten sam stopień, więc połącz je. Zjednoczcie tych, którzy mają te same stopnie naukowe
  7. Mapuj kolejne węzły. Mapuj pozostałe węzły
  8. Ponownie, 52 i 21 mają ten sam stopień, więc zjednoczcie ich z tymi, którzy mają te same stopnie
  9. Podobnie, zjednoczcie 21 i 18. Zjednoczcie tych, którzy mają te same stopnie
  10. Mapuj pozostały korzeń. Mapuj pozostałe węzły
  11. Ostatnia kupa to. Ostateczna sterta Fibonacciego

Zmniejszanie klucza i usuwanie węzła

Są to najważniejsze operacje, które są omówione w operacjach Zmniejsz klucz i Usuń węzeł.

Przykłady w Pythonie, Javie i C / C ++

Python Java C + 
 # Fibonacci Heap in python import math # Creating fibonacci tree class FibonacciTree: def __init__(self, value): self.value = value self.child = () self.order = 0 # Adding tree at the end of the tree def add_at_end(self, t): self.child.append(t) self.order = self.order + 1 # Creating Fibonacci heap class FibonacciHeap: def __init__(self): self.trees = () self.least = None self.count = 0 # Insert a node def insert_node(self, value): new_tree = FibonacciTree(value) self.trees.append(new_tree) if (self.least is None or value y.value: x, y = y, x x.add_at_end(y) aux(order) = None order = order + 1 aux(order) = x self.least = None for k in aux: if k is not None: self.trees.append(k) if (self.least is None or k.value < self.least.value): self.least = k def floor_log(x): return math.frexp(x)(1) - 1 fibonacci_heap = FibonacciHeap() fibonacci_heap.insert_node(7) fibonacci_heap.insert_node(3) fibonacci_heap.insert_node(17) fibonacci_heap.insert_node(24) print('the minimum value of the fibonacci heap: ()'.format(fibonacci_heap.get_min())) print('the minimum value removed: ()'.format(fibonacci_heap.extract_min())) 
 // Operations on Fibonacci Heap in Java // Node creation class node ( node parent; node left; node right; node child; int degree; boolean mark; int key; public node() ( this.degree = 0; this.mark = false; this.parent = null; this.left = this; this.right = this; this.child = null; this.key = Integer.MAX_VALUE; ) node(int x) ( this(); this.key = x; ) void set_parent(node x) ( this.parent = x; ) node get_parent() ( return this.parent; ) void set_left(node x) ( this.left = x; ) node get_left() ( return this.left; ) void set_right(node x) ( this.right = x; ) node get_right() ( return this.right; ) void set_child(node x) ( this.child = x; ) node get_child() ( return this.child; ) void set_degree(int x) ( this.degree = x; ) int get_degree() ( return this.degree; ) void set_mark(boolean m) ( this.mark = m; ) boolean get_mark() ( return this.mark; ) void set_key(int x) ( this.key = x; ) int get_key() ( return this.key; ) ) public class fibHeap ( node min; int n; boolean trace; node found; public boolean get_trace() ( return trace; ) public void set_trace(boolean t) ( this.trace = t; ) public static fibHeap create_heap() ( return new fibHeap(); ) fibHeap() ( min = null; n = 0; trace = false; ) private void insert(node x) ( if (min == null) ( min = x; x.set_left(min); x.set_right(min); ) else ( x.set_right(min); x.set_left(min.get_left()); min.get_left().set_right(x); min.set_left(x); if (x.get_key() "); temp = temp.get_right(); ) while (temp != c); System.out.print(")"); ) ) public static void merge_heap(fibHeap H1, fibHeap H2, fibHeap H3) ( H3.min = H1.min; if (H1.min != null && H2.min != null) ( node t1 = H1.min.get_left(); node t2 = H2.min.get_left(); H1.min.set_left(t2); t1.set_right(H2.min); H2.min.set_left(t1); t2.set_right(H1.min); ) if (H1.min == null || (H2.min != null && H2.min.get_key() < H1.min.get_key())) H3.min = H2.min; H3.n = H1.n + H2.n; ) public int find_min() ( return this.min.get_key(); ) private void display_node(node z) ( System.out.println("right: " + ((z.get_right() == null) ? "-1" : z.get_right().get_key())); System.out.println("left: " + ((z.get_left() == null) ? "-1" : z.get_left().get_key())); System.out.println("child: " + ((z.get_child() == null) ? "-1" : z.get_child().get_key())); System.out.println("degree " + z.get_degree()); ) public int extract_min() ( node z = this.min; if (z != null) ( node c = z.get_child(); node k = c, p; if (c != null) ( do ( p = c.get_right(); insert(c); c.set_parent(null); c = p; ) while (c != null && c != k); ) z.get_left().set_right(z.get_right()); z.get_right().set_left(z.get_left()); z.set_child(null); if (z == z.get_right()) this.min = null; else ( this.min = z.get_right(); this.consolidate(); ) this.n -= 1; return z.get_key(); ) return Integer.MAX_VALUE; ) public void consolidate() ( double phi = (1 + Math.sqrt(5)) / 2; int Dofn = (int) (Math.log(this.n) / Math.log(phi)); node() A = new node(Dofn + 1); for (int i = 0; i y.get_key()) ( node temp = x; x = y; y = temp; w = x; ) fib_heap_link(y, x); check = x; A(d) = null; d += 1; ) A(d) = x; w = w.get_right(); ) while (w != null && w != check); this.min = null; for (int i = 0; i <= Dofn; ++i) ( if (A(i) != null) ( insert(A(i)); ) ) ) ) // Linking operation private void fib_heap_link(node y, node x) ( y.get_left().set_right(y.get_right()); y.get_right().set_left(y.get_left()); node p = x.get_child(); if (p == null) ( y.set_right(y); y.set_left(y); ) else ( y.set_right(p); y.set_left(p.get_left()); p.get_left().set_right(y); p.set_left(y); ) y.set_parent(x); x.set_child(y); x.set_degree(x.get_degree() + 1); y.set_mark(false); ) // Search operation private void find(int key, node c) ( if (found != null || c == null) return; else ( node temp = c; do ( if (key == temp.get_key()) found = temp; else ( node k = temp.get_child(); find(key, k); temp = temp.get_right(); ) ) while (temp != c && found == null); ) ) public node find(int k) ( found = null; find(k, this.min); return found; ) public void decrease_key(int key, int nval) ( node x = find(key); decrease_key(x, nval); ) // Decrease key operation private void decrease_key(node x, int k) ( if (k> x.get_key()) return; x.set_key(k); node y = x.get_parent(); if (y != null && x.get_key() < y.get_key()) ( cut(x, y); cascading_cut(y); ) if (x.get_key() < min.get_key()) min = x; ) // Cut operation private void cut(node x, node y) ( x.get_right().set_left(x.get_left()); x.get_left().set_right(x.get_right()); y.set_degree(y.get_degree() - 1); x.set_right(null); x.set_left(null); insert(x); x.set_parent(null); x.set_mark(false); ) private void cascading_cut(node y) ( node z = y.get_parent(); if (z != null) ( if (y.get_mark() == false) y.set_mark(true); else ( cut(y, z); cascading_cut(z); ) ) ) // Delete operations public void delete(node x) ( decrease_key(x, Integer.MIN_VALUE); int p = extract_min(); ) public static void main(String() args) ( fibHeap obj = create_heap(); obj.insert(7); obj.insert(26); obj.insert(30); obj.insert(39); obj.insert(10); obj.display(); System.out.println(obj.extract_min()); obj.display(); System.out.println(obj.extract_min()); obj.display(); System.out.println(obj.extract_min()); obj.display(); System.out.println(obj.extract_min()); obj.display(); System.out.println(obj.extract_min()); obj.display(); ) )
 // Operations on a Fibonacci heap in C #include #include #include #include typedef struct _NODE ( int key; int degree; struct _NODE *left_sibling; struct _NODE *right_sibling; struct _NODE *parent; struct _NODE *child; bool mark; bool visited; ) NODE; typedef struct fibanocci_heap ( int n; NODE *min; int phi; int degree; ) FIB_HEAP; FIB_HEAP *make_fib_heap(); void insertion(FIB_HEAP *H, NODE *new, int val); NODE *extract_min(FIB_HEAP *H); void consolidate(FIB_HEAP *H); void fib_heap_link(FIB_HEAP *H, NODE *y, NODE *x); NODE *find_min_node(FIB_HEAP *H); void decrease_key(FIB_HEAP *H, NODE *node, int key); void cut(FIB_HEAP *H, NODE *node_to_be_decrease, NODE *parent_node); void cascading_cut(FIB_HEAP *H, NODE *parent_node); void Delete_Node(FIB_HEAP *H, int dec_key); FIB_HEAP *make_fib_heap() ( FIB_HEAP *H; H = (FIB_HEAP *)malloc(sizeof(FIB_HEAP)); H->n = 0; H->min = NULL; H->phi = 0; H->degree = 0; return H; ) // Printing the heap void print_heap(NODE *n) ( NODE *x; for (x = n;; x = x->right_sibling) ( if (x->child == NULL) ( printf("node with no child (%d) ", x->key); ) else ( printf("NODE(%d) with child (%d)", x->key, x->child->key); print_heap(x->child); ) if (x->right_sibling == n) ( break; ) ) ) // Inserting nodes void insertion(FIB_HEAP *H, NODE *new, int val) ( new = (NODE *)malloc(sizeof(NODE)); new->key = val; new->degree = 0; new->mark = false; new->parent = NULL; new->child = NULL; new->visited = false; new->left_sibling = new; new->right_sibling = new; if (H->min == NULL) ( H->min = new; ) else ( H->min->left_sibling->right_sibling = new; new->right_sibling = H->min; new->left_sibling = H->min->left_sibling; H->min->left_sibling = new; if (new->key min->key) ( H->min = new; ) ) (H->n)++; ) // Find min node NODE *find_min_node(FIB_HEAP *H) ( if (H == NULL) ( printf(" Fibonacci heap not yet created "); return NULL; ) else return H->min; ) // Union operation FIB_HEAP *unionHeap(FIB_HEAP *H1, FIB_HEAP *H2) ( FIB_HEAP *Hnew; Hnew = make_fib_heap(); Hnew->min = H1->min; NODE *temp1, *temp2; temp1 = Hnew->min->right_sibling; temp2 = H2->min->left_sibling; Hnew->min->right_sibling->left_sibling = H2->min->left_sibling; Hnew->min->right_sibling = H2->min; H2->min->left_sibling = Hnew->min; temp2->right_sibling = temp1; if ((H1->min == NULL) || (H2->min != NULL && H2->min->key min->key)) Hnew->min = H2->min; Hnew->n = H1->n + H2->n; return Hnew; ) // Calculate the degree int cal_degree(int n) ( int count = 0; while (n> 0) ( n = n / 2; count++; ) return count; ) // Consolidate function void consolidate(FIB_HEAP *H) ( int degree, i, d; degree = cal_degree(H->n); NODE *A(degree), *x, *y, *z; for (i = 0; i min; do ( d = x->degree; while (A(d) != NULL) ( y = A(d); if (x->key> y->key) ( NODE *exchange_help; exchange_help = x; x = y; y = exchange_help; ) if (y == H->min) H->min = x; fib_heap_link(H, y, x); if (y->right_sibling == x) H->min = x; A(d) = NULL; d++; ) A(d) = x; x = x->right_sibling; ) while (x != H->min); H->min = NULL; for (i = 0; i left_sibling = A(i); A(i)->right_sibling = A(i); if (H->min == NULL) ( H->min = A(i); ) else ( H->min->left_sibling->right_sibling = A(i); A(i)->right_sibling = H->min; A(i)->left_sibling = H->min->left_sibling; H->min->left_sibling = A(i); if (A(i)->key min->key) ( H->min = A(i); ) ) if (H->min == NULL) ( H->min = A(i); ) else if (A(i)->key min->key) ( H->min = A(i); ) ) ) ) // Linking void fib_heap_link(FIB_HEAP *H, NODE *y, NODE *x) ( y->right_sibling->left_sibling = y->left_sibling; y->left_sibling->right_sibling = y->right_sibling; if (x->right_sibling == x) H->min = x; y->left_sibling = y; y->right_sibling = y; y->parent = x; if (x->child == NULL) ( x->child = y; ) y->right_sibling = x->child; y->left_sibling = x->child->left_sibling; x->child->left_sibling->right_sibling = y; x->child->left_sibling = y; if ((y->key) child->key)) x->child = y; (x->degree)++; ) // Extract min NODE *extract_min(FIB_HEAP *H) ( if (H->min == NULL) printf(" The heap is empty"); else ( NODE *temp = H->min; NODE *pntr; pntr = temp; NODE *x = NULL; if (temp->child != NULL) ( x = temp->child; do ( pntr = x->right_sibling; (H->min->left_sibling)->right_sibling = x; x->right_sibling = H->min; x->left_sibling = H->min->left_sibling; H->min->left_sibling = x; if (x->key min->key) H->min = x; x->parent = NULL; x = pntr; ) while (pntr != temp->child); ) (temp->left_sibling)->right_sibling = temp->right_sibling; (temp->right_sibling)->left_sibling = temp->left_sibling; H->min = temp->right_sibling; if (temp == temp->right_sibling && temp->child == NULL) H->min = NULL; else ( H->min = temp->right_sibling; consolidate(H); ) H->n = H->n - 1; return temp; ) return H->min; ) void cut(FIB_HEAP *H, NODE *node_to_be_decrease, NODE *parent_node) ( NODE *temp_parent_check; if (node_to_be_decrease == node_to_be_decrease->right_sibling) parent_node->child = NULL; node_to_be_decrease->left_sibling->right_sibling = node_to_be_decrease->right_sibling; node_to_be_decrease->right_sibling->left_sibling = node_to_be_decrease->left_sibling; if (node_to_be_decrease == parent_node->child) parent_node->child = node_to_be_decrease->right_sibling; (parent_node->degree)--; node_to_be_decrease->left_sibling = node_to_be_decrease; node_to_be_decrease->right_sibling = node_to_be_decrease; H->min->left_sibling->right_sibling = node_to_be_decrease; node_to_be_decrease->right_sibling = H->min; node_to_be_decrease->left_sibling = H->min->left_sibling; H->min->left_sibling = node_to_be_decrease; node_to_be_decrease->parent = NULL; node_to_be_decrease->mark = false; ) void cascading_cut(FIB_HEAP *H, NODE *parent_node) ( NODE *aux; aux = parent_node->parent; if (aux != NULL) ( if (parent_node->mark == false) ( parent_node->mark = true; ) else ( cut(H, parent_node, aux); cascading_cut(H, aux); ) ) ) void decrease_key(FIB_HEAP *H, NODE *node_to_be_decrease, int new_key) ( NODE *parent_node; if (H == NULL) ( printf(" FIbonacci heap not created "); return; ) if (node_to_be_decrease == NULL) ( printf("Node is not in the heap"); ) else ( if (node_to_be_decrease->key key = new_key; parent_node = node_to_be_decrease->parent; if ((parent_node != NULL) && (node_to_be_decrease->key key)) ( printf(" cut called"); cut(H, node_to_be_decrease, parent_node); printf(" cascading cut called"); cascading_cut(H, parent_node); ) if (node_to_be_decrease->key min->key) ( H->min = node_to_be_decrease; ) ) ) ) void *find_node(FIB_HEAP *H, NODE *n, int key, int new_key) ( NODE *find_use = n; NODE *f = NULL; find_use->visited = true; if (find_use->key == key) ( find_use->visited = false; f = find_use; decrease_key(H, f, new_key); ) if (find_use->child != NULL) ( find_node(H, find_use->child, key, new_key); ) if ((find_use->right_sibling->visited != true)) ( find_node(H, find_use->right_sibling, key, new_key); ) find_use->visited = false; ) FIB_HEAP *insertion_procedure() ( FIB_HEAP *temp; int no_of_nodes, ele, i; NODE *new_node; temp = (FIB_HEAP *)malloc(sizeof(FIB_HEAP)); temp = NULL; if (temp == NULL) ( temp = make_fib_heap(); ) printf(" enter number of nodes to be insert = "); scanf("%d", &no_of_nodes); for (i = 1; i min, dec_key, -5000); p = extract_min(H); if (p != NULL) printf(" Node deleted"); else printf(" Node not deleted:some error"); ) int main(int argc, char **argv) ( NODE *new_node, *min_node, *extracted_min, *node_to_be_decrease, *find_use; FIB_HEAP *heap, *h1, *h2; int operation_no, new_key, dec_key, ele, i, no_of_nodes; heap = (FIB_HEAP *)malloc(sizeof(FIB_HEAP)); heap = NULL; while (1) ( printf(" Operations 1. Create Fibonacci heap 2. Insert nodes into fibonacci heap 3. Find min 4. Union 5. Extract min 6. Decrease key 7.Delete node 8. print heap 9. exit enter operation_no = "); scanf("%d", &operation_no); switch (operation_no) ( case 1: heap = make_fib_heap(); break; case 2: if (heap == NULL) ( heap = make_fib_heap(); ) printf(" enter number of nodes to be insert = "); scanf("%d", &no_of_nodes); for (i = 1; i key); break; case 4: if (heap == NULL) ( printf(" no FIbonacci heap created "); break; ) h1 = insertion_procedure(); heap = unionHeap(heap, h1); printf("Unified Heap:"); print_heap(heap->min); break; case 5: if (heap == NULL) printf("Empty Fibonacci heap"); else ( extracted_min = extract_min(heap); printf(" min value = %d", extracted_min->key); printf(" Updated heap: "); print_heap(heap->min); ) break; case 6: if (heap == NULL) printf("Fibonacci heap is empty"); else ( printf(" node to be decreased = "); scanf("%d", &dec_key); printf(" enter the new key = "); scanf("%d", &new_key); find_use = heap->min; find_node(heap, find_use, dec_key, new_key); printf(" Key decreased- Corresponding heap:"); print_heap(heap->min); ) break; case 7: if (heap == NULL) printf("Fibonacci heap is empty"); else ( printf(" Enter node key to be deleted = "); scanf("%d", &dec_key); Delete_Node(heap, dec_key); printf(" Node Deleted- Corresponding heap:"); print_heap(heap->min); break; ) case 8: print_heap(heap->min); break; case 9: free(new_node); free(heap); exit(0); default: printf("Invalid choice "); ) ) )
 // Operations on a Fibonacci heap in C++ #include #include #include using namespace std; // Node creation struct node ( int n; int degree; node *parent; node *child; node *left; node *right; char mark; char C; ); // Implementation of Fibonacci heap class FibonacciHeap ( private: int nH; node *H; public: node *InitializeHeap(); int Fibonnaci_link(node *, node *, node *); node *Create_node(int); node *Insert(node *, node *); node *Union(node *, node *); node *Extract_Min(node *); int Consolidate(node *); int Display(node *); node *Find(node *, int); int Decrease_key(node *, int, int); int Delete_key(node *, int); int Cut(node *, node *, node *); int Cascase_cut(node *, node *); FibonacciHeap() ( H = InitializeHeap(); ) ); // Initialize heap node *FibonacciHeap::InitializeHeap() ( node *np; np = NULL; return np; ) // Create node node *FibonacciHeap::Create_node(int value) ( node *x = new node; x->n = value; return x; ) // Insert node node *FibonacciHeap::Insert(node *H, node *x) ( x->degree = 0; x->parent = NULL; x->child = NULL; x->left = x; x->right = x; x->mark = 'F'; x->C = 'N'; if (H != NULL) ( (H->left)->right = x; x->right = H; x->left = H->left; H->left = x; if (x->n n) H = x; ) else ( H = x; ) nH = nH + 1; return H; ) // Create linking int FibonacciHeap::Fibonnaci_link(node *H1, node *y, node *z) ( (y->left)->right = y->right; (y->right)->left = y->left; if (z->right == z) H1 = z; y->left = y; y->right = y; y->parent = z; if (z->child == NULL) z->child = y; y->right = z->child; y->left = (z->child)->left; ((z->child)->left)->right = y; (z->child)->left = y; if (y->n child)->n) z->child = y; z->degree++; ) // Union Operation node *FibonacciHeap::Union(node *H1, node *H2) ( node *np; node *H = InitializeHeap(); H = H1; (H->left)->right = H2; (H2->left)->right = H; np = H->left; H->left = H2->left; H2->left = np; return H; ) // Display the heap int FibonacciHeap::Display(node *H) ( node *p = H; if (p == NULL) ( cout << "Empty Heap" << endl; return 0; ) cout << "Root Nodes: " << endl; do ( cout  right; if (p != H) ( cout <"; ) ) while (p != H && p->right != NULL); cout <  child != NULL) x = z->child; if (x != NULL) ( ptr = x; do ( np = x->right; (H1->left)->right = x; x->right = H1; x->left = H1->left; H1->left = x; if (x->n n) H1 = x; x->parent = NULL; x = np; ) while (np != ptr); ) (z->left)->right = z->right; (z->right)->left = z->left; H1 = z->right; if (z == z->right && z->child == NULL) H = NULL; else ( H1 = z->right; Consolidate(H1); ) nH = nH - 1; return p; ) // Consolidation Function int FibonacciHeap::Consolidate(node *H1) ( int d, i; float f = (log(nH)) / (log(2)); int D = f; node *A(D); for (i = 0; i right; d = x->degree; while (A(d) != NULL) ( y = A(d); if (x->n> y->n) ( np = x; x = y; y = np; ) if (y == H1) H1 = x; Fibonnaci_link(H1, y, x); if (x->right == x) H1 = x; A(d) = NULL; d = d + 1; ) A(d) = x; x = x->right; ) while (x != H1); H = NULL; for (int j = 0; j left = A(j); A(j)->right = A(j); if (H != NULL) ( (H->left)->right = A(j); A(j)->right = H; A(j)->left = H->left; H->left = A(j); if (A(j)->n n) H = A(j); ) else ( H = A(j); ) if (H == NULL) H = A(j); else if (A(j)->n n) H = A(j); ) ) ) // Decrease Key Operation int FibonacciHeap::Decrease_key(node *H1, int x, int k) ( node *y; if (H1 == NULL) ( cout << "The Heap is Empty" << endl; return 0; ) node *ptr = Find(H1, x); if (ptr == NULL) ( cout << "Node not found in the Heap"  parent; if (y != NULL && ptr->n n) ( Cut(H1, ptr, y); Cascase_cut(H1, y); ) if (ptr->n n) H = ptr; return 0; ) // Cutting Function int FibonacciHeap::Cut(node *H1, node *x, node *y) ( if (x == x->right) y->child = NULL; (x->left)->right = x->right; (x->right)->left = x->left; if (x == y->child) y->child = x->right; y->degree = y->degree - 1; x->right = x; x->left = x; (H1->left)->right = x; x->right = H1; x->left = H1->left; H1->left = x; x->parent = NULL; x->mark = 'F'; ) // Cascade cut int FibonacciHeap::Cascase_cut(node *H1, node *y) ( node *z = y->parent; if (z != NULL) ( if (y->mark == 'F') ( y->mark = 'T'; ) else ( Cut(H1, y, z); Cascase_cut(H1, z); ) ) ) // Search function node *FibonacciHeap::Find(node *H, int k) ( node *x = H; x->C = 'Y'; node *p = NULL; if (x->n == k) ( p = x; x->C = 'N'; return p; ) if (p == NULL) ( if (x->child != NULL) p = Find(x->child, k); if ((x->right)->C != 'Y') p = Find(x->right, k); ) x->C = 'N'; return p; ) // Deleting key int FibonacciHeap::Delete_key(node *H1, int k) ( node *np = NULL; int t; t = Decrease_key(H1, k, -5000); if (!t) np = Extract_Min(H); if (np != NULL) cout << "Key Deleted" << endl; else cout << "Key not Deleted" << endl; return 0; ) int main() ( int n, m, l; FibonacciHeap fh; node *p; node *H; H = fh.InitializeHeap(); p = fh.Create_node(7); H = fh.Insert(H, p); p = fh.Create_node(3); H = fh.Insert(H, p); p = fh.Create_node(17); H = fh.Insert(H, p); p = fh.Create_node(24); H = fh.Insert(H, p); fh.Display(H); p = fh.Extract_Min(H); if (p != NULL) cout << "The node with minimum key: "

Complexities

Insertion O(1)
Find Min O(1)
Union O(1)
Extract Min O(log n)
Decrease Key O(1)
Delete Node O(log n)

Fibonacci Heap Applications

  1. To improve the asymptotic running time of Dijkstra's algorithm.

Interesujące artykuły...