Fibonacci hunnik

Selles õpetuses saate teada, mis on Fibonacci hunnik. Samuti leiate toimivaid näiteid erinevatest toimingutest fibonacci hunnikus C, C ++, Java ja Python.

Fibonacci kuhi on binoomhunniku modifitseeritud vorm, millel on tõhusamad kuhjaoperatsioonid kui see, mida toetavad binoom- ja binaarkuhjad.

Erinevalt binaarhunnikust võib sõlmel olla rohkem kui kaks last.

Fibonacci kuhja nimetatakse fibonacci kuhjaks, kuna puud on ehitatud nii, et järjekorraga n puul on vähemalt Fn+2sõlmed, kus Fn+2on (n + 2)ndFibonacci number.

Fibonacci hunnik

Fibonacci kuhja omadused

Fibonacci kuhja olulised omadused on:

  1. See on hulk kuhjaga tellitud puid. (st vanem on alati väiksem kui lapsed.)
  2. Minimaalse elemendi sõlmes hoitakse kursorit.
  3. See koosneb märgitud sõlmede komplektist. (Vähenda klahvitoimingut)
  4. Puud Fibonacci kuhjas on korrastamata, kuid juurdunud.

Sõlmede mälu kujutamine Fibonacci kuhjas

Kõigi puude juured on kiiremaks juurdepääsuks ühendatud. Vanemasõlme alamsõlmed on omavahel ühendatud ümmarguse topeltlingitud loendi kaudu, nagu allpool näidatud.

Kaks korda lingitud ümmarguse loendi kasutamisel on kaks peamist eelist.

  1. Puust sõlme kustutamine võtab O(1)aega.
  2. Kahe sellise loendi liitmine võtab O(1)aega.
Fibonacci kuhja struktuur

Operatsioonid Fibonacci kuhil

Sisestamine

Algoritm

 sisesta (H, x) kraad (x) = 0 p (x) = NIL laps (x) = NIL vasak (x) = x parem (x) = x märk (x) = FALSE ühenda x-i sisaldav juurte loend koos juurega loend H, kui min (H) == NIL või klahv (x) <võti (min (H)), siis min (H) = xn (H) = n (H) + 1

Sõlme sisestamine juba olemasolevasse kuhja toimib järgmiselt.

  1. Looge elemendile uus sõlm.
  2. Kontrollige, kas hunnik on tühi.
  3. Kui hunnik on tühi, määrake uus sõlm juursõlmeks ja märkige see min.
  4. Muul juhul sisestage sõlm juurnimekirja ja värskendage min.
Lisamise näide

Leidke Min

Minimaalse elemendi annab alati min-osuti.

Liit

Kahe fibonaccihunniku liit koosneb järgmistest etappidest.

  1. Liitke mõlema kuhi juured.
  2. Värskendage min valides uutest juurloenditest minimaalse võtme.
Kahe kuhja liit

Väljavõte Min

See on fibonacci kuhja kõige olulisem operatsioon. Selle toimingu korral eemaldatakse hunnikust minimaalse väärtusega sõlm ja puu kohandatakse uuesti.

Järgitakse järgmisi samme:

  1. Kustutage min sõlm.
  2. Määrake minikursor juurte loendi järgmise juure juurde.
  3. Enne kustutamist looge massiivi suurus, mis võrdub kuhja puude maksimaalse astmega.
  4. Tehke järgmist (sammud 5–7), kuni pole mitu sama astmega juuri.
  5. Kaardistage praeguse juure (min-osuti) aste massiivi kraadini.
  6. Kaardista järgmise juure aste massiivi kraadini.
  7. Kui samal astmel on rohkem kui kaks vastendamist, rakendage nendele juurtele liidetoimingut nii, et min-kuhja omadus säiliks (st miinimum on juurtes).

Ülaltoodud sammude rakendamist saab mõista allpool toodud näites.

  1. Teostame allpool oleva kuhjaga ekstrakt-min operatsiooni. Fibonacci hunnik
  2. Kustutage min-sõlm, lisage kõik selle alamsõlmed juuriloendisse ja määrake min-osuti juurnimekirja järgmisele juurele. Kustutage min sõlm
  3. Puu maksimaalne aste on 3. Looge massiiviga massiivi suurus 4 ja kaardistage järgmiste juurte aste. Loo massiiv
  4. Siin on 23. ja 7. kraadi ühesugused, nii et ühendage need. Ühendage need, kellel on sama kraad
  5. Jällegi on 7-l ja 17-l samad kraadid, nii et ühendage ka need. Ühendage need, kellel on sama kraad
  6. Jällegi on 7-l ja 24-l sama aste, nii et ühendage nad. Ühendage need, kellel on sama kraad
  7. Järgmiste sõlmede kaardistamine. Kaardistage ülejäänud sõlmed
  8. Jällegi on 52-l ja 21-l sama aste, nii et ühendage need ja ühendage need, kellel on sama aste
  9. Samamoodi ühendage 21. ja 18. Ühendage need, kellel on sama kraad
  10. Kaardistage järelejäänud juur. Kaardistage ülejäänud sõlmed
  11. Viimane hunnik on. Lõplik fibonacci hunnik

Võtme vähendamine ja sõlme kustutamine

Need on kõige olulisemad toimingud, mida käsitletakse võtmete vähendamise ja sõlme kustutamise operatsioonides.

Pythoni, Java ja C / C ++ näited

Python Java C 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.

Huvitavad Artiklid...