Фибоначијева гомила

У овом упутству ћете научити шта је Фибоначијева гомила. Такође ћете наћи радне примере различитих операција на фибоначијевој гомили у Ц, Ц ++, Јава и Питхон.

Фибоначијева гомила је модификовани облик биномне гомиле са ефикаснијим операцијама гомиле од оне коју подржавају биномна и бинарна гомила.

За разлику од бинарне хрпе, чвор може имати више од двоје деце.

Гомила фибоначија назива се фибоначијева хрпа јер су стабла конструисана тако да дрво реда н има најмање Fn+2чворове у себи, где Fn+2је (n + 2)ndФибоначијев број.

Фибоначијева гомила

Особине Фибоначијеве гомиле

Важна својства Фибоначијеве гомиле су:

  1. То је сет од најмање дрвећа по наруџбини . (тј. Родитељ је увек мањи од деце.)
  2. Показивач се одржава на минималном чвору елемента.
  3. Састоји се од скупа означених чворова. (Смањи рад тастера)
  4. Дрвеће у фибоначијевој гомили је неуређено, али укорењено.

Репрезентација чворова у меморији на Фибоначијевој гомили

Корени свих стабала повезани су за бржи приступ. Подређени чворови родитељског чвора повезани су међусобно путем кружне двоструко повезане листе као што је приказано доле.

Две су главне предности употребе кружне двоструко повезане листе.

  1. Брисање чвора са стабла захтева O(1)време.
  2. Спајање две такве листе захтева O(1)време.
Структура Фибоначијеве гомиле

Операције на Фибоначијевој гомили

Уметање

Алгоритам

 убаци (Х, к) степен (к) = 0 п (к) = НИЛ дете (к) = НИЛ лево (к) = к десно (к) = к ознака (к) = ФАЛСЕ спаја коренску листу која садржи к са кореном навести Х ако је мин (Х) == НИЛ или тастер (к) <тастер (мин (Х)), а затим мин (Х) = кн (Х) = н (Х) + 1

Уметање чвора у већ постојећу гомилу следи кораке у наставку.

  1. Направите нови чвор за елемент.
  2. Проверите да ли је гомила празна.
  3. Ако је гомила празна, поставите нови чвор као коријенски чвор и означите га мин.
  4. Иначе, убаците чвор у основну листу и ажурирајте мин.
Пример уметања

Пронађи Мин

Минимални елемент увек даје показивач мин.

унија

Спајање две фибоначијеве гомиле састоји се од следећих корака.

  1. Спојите корене обе гомиле.
  2. Ажурирајте мин одабиром минималног кључа са нових коренских листа.
Унија две гомиле

Екстракт Мин

То је најважнија операција на фибоначијевој гомили. У овој операцији чвор са минималном вредношћу уклања се из гомиле и стабло се поново прилагођава.

Следе следећи кораци:

  1. Избришите мин чвор.
  2. Поставите мин-показивач на следећи корен на коренској листи.
  3. Направите низ величине једнак максималном степену стабала у гомили пре брисања.
  4. Урадите следеће (кораци 5-7) док не буде више корена са истим степеном.
  5. Мапирајте степен тренутног корена (мин-показивач) на степен у низу.
  6. Мапирајте степен следећег корена на степен у низу.
  7. Ако постоји више од два пресликавања за исти степен, примените операцију удруживања на те корене тако да се одржава својство мин-хеап (тј. Минимум је у корену).

Примена горе наведених корака може се разумети у примеру испод.

  1. Извешћемо операцију извлачења-мин на хрпи испод. Фибоначијева гомила
  2. Избришите мин чвор, додајте све његове подређене чворове на коренску листу и поставите мин показивач на следећи корен на коренској листи. Избришите мин чвор
  3. Максимални степен у стаблу је 3. Створите низ величине 4 и мапирајте степен следећих корена низом. Направите низ
  4. Овде 23 и 7 имају исте степене, па их уједините. Уједините оне који имају исте дипломе
  5. Опет, 7 и 17 имају исте степене, па их и уједините. Уједините оне који имају исте дипломе
  6. Опет 7 и 24 имају исти степен, па их уједините. Уједините оне који имају исте дипломе
  7. Мапирајте следеће чворове. Мапирајте преостале чворове
  8. Опет, 52 и 21 имају исти степен, па их уједините Уједините оне који имају исте степене
  9. Слично томе, уједините 21 и 18. Уједините оне који имају исте степене
  10. Мапирајте преостали корен. Мапирајте преостале чворове
  11. Коначна гомила је. Завршна гомила фибоначија

Смањивање кључа и брисање чвора

То су најважније операције о којима се говори у операцијама Смањивање кључа и Брисање чворова.

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц + 
 # 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.

Занимљиви Чланци...