Fibonacci Heap

Trong hướng dẫn này, bạn sẽ tìm hiểu Fibonacci Heap là gì. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của các hoạt động khác nhau trên một đống fibonacci trong C, C ++, Java và Python.

Fibonacci heap là một dạng sửa đổi của heap nhị thức với các hoạt động trên heap hiệu quả hơn so với heap nhị thức và nhị phân được hỗ trợ.

Không giống như đống nhị phân, một nút có thể có nhiều hơn hai nút con.

Các đống Fibonacci được gọi là một fibonacci đống vì cây được xây dựng theo cách như vậy mà một cây trật tự n có ít nhất Fn+2nút trong nó, nơi Fn+2là (n + 2)ndsố Fibonacci.

Fibonacci Heap

Thuộc tính của một đống Fibonacci

Các thuộc tính quan trọng của một đống Fibonacci là:

  1. Nó là một tập hợp các cây theo thứ tự đống nhỏ. (nghĩa là Bố mẹ luôn nhỏ hơn con cái.)
  2. Một con trỏ được duy trì ở nút phần tử tối thiểu.
  3. Nó bao gồm một tập hợp các nút được đánh dấu. (Giảm thao tác phím)
  4. Các cây trong đống Fibonacci không có thứ tự nhưng có gốc.

Biểu diễn bộ nhớ của các nút trong một đống Fibonacci

Rễ của tất cả các cây được liên kết với nhau để tiếp cận nhanh hơn. Các nút con của nút cha được kết nối với nhau thông qua một danh sách liên kết kép hình tròn như hình dưới đây.

Có hai ưu điểm chính của việc sử dụng danh sách liên kết kép vòng tròn.

  1. Xóa một nút khỏi cây sẽ mất O(1)thời gian.
  2. Việc ghép hai danh sách như vậy cần nhiều O(1)thời gian.
Cấu trúc đống Fibonacci

Các hoạt động trên Fibonacci Heap

Chèn

Thuật toán

 insert (H, x) Deg (x) = 0 p (x) = NIL con (x) = NIL left (x) = x right (x) = x mark (x) = FALSE nối danh sách gốc chứa x với root liệt kê H nếu min (H) == NIL hoặc key (x) <key (min (H)) thì min (H) = xn (H) = n (H) + 1

Việc chèn một nút vào một heap đã tồn tại sẽ thực hiện theo các bước bên dưới.

  1. Tạo một nút mới cho phần tử.
  2. Kiểm tra xem heap có trống không.
  3. Nếu heap trống, hãy đặt nút mới làm nút gốc và đánh dấu nó là min.
  4. Nếu không, chèn nút vào danh sách gốc và cập nhật min.
Ví dụ về chèn

Tìm Min

Phần tử nhỏ nhất luôn được cho bởi con trỏ min.

liên hiệp

Sự kết hợp của hai đống fibonacci bao gồm các bước sau.

  1. Nối rễ của cả hai đống.
  2. Cập nhật tối thiểu bằng cách chọn một khóa tối thiểu từ danh sách gốc mới.
Sự kết hợp của hai đống

Trích xuất Min

Đây là hoạt động quan trọng nhất trên một đống fibonacci. Trong thao tác này, nút có giá trị nhỏ nhất được xóa khỏi đống và cây được điều chỉnh lại.

Các bước sau được thực hiện theo:

  1. Xóa nút min.
  2. Đặt con trỏ min tới gốc tiếp theo trong danh sách gốc.
  3. Tạo một mảng có kích thước bằng với mức độ lớn nhất của các cây trong đống trước khi xóa.
  4. Làm như sau (bước 5-7) cho đến khi không còn nhiều rễ có cùng mức độ.
  5. Ánh xạ mức của gốc hiện tại (con trỏ tối thiểu) với mức trong mảng.
  6. Ánh xạ mức độ của gốc tiếp theo với mức độ trong mảng.
  7. Nếu có nhiều hơn hai ánh xạ cho cùng một mức độ, thì áp dụng phép toán liên hợp cho các gốc đó sao cho thuộc tính min-heap được duy trì (nghĩa là giá trị nhỏ nhất ở gốc).

Việc triển khai các bước trên có thể được hiểu trong ví dụ dưới đây.

  1. Chúng tôi sẽ thực hiện thao tác giải nén tối thiểu trên đống bên dưới. Fibonacci Heap
  2. Xóa nút min, thêm tất cả các nút con của nó vào danh sách gốc và đặt con trỏ min thành gốc tiếp theo trong danh sách gốc. Xóa nút tối thiểu
  3. Mức độ tối đa trong cây là 3. Tạo một mảng có kích thước 4 và ánh xạ mức độ của các gốc tiếp theo với mảng. Tạo một mảng
  4. Ở đây, 23 và 7 có cùng độ, vì vậy hãy hợp nhất chúng lại. Đoàn kết những người có cùng bằng cấp
  5. Một lần nữa, 7 và 17 có cùng độ, vì vậy hãy đoàn kết chúng lại. Đoàn kết những người có cùng bằng cấp
  6. Một lần nữa 7 và 24 có cùng mức độ, vì vậy hãy hợp nhất chúng. Đoàn kết những người có cùng bằng cấp
  7. Lập bản đồ các nút tiếp theo. Ánh xạ các nút còn lại
  8. Một lần nữa, 52 và 21 có cùng bằng cấp, vì vậy hãy hợp nhất chúng Hợp nhất những người có cùng bằng cấp
  9. Tương tự, hợp nhất 21 và 18. Hợp nhất những người có cùng bằng cấp
  10. Ánh xạ gốc còn lại. Ánh xạ các nút còn lại
  11. Đống cuối cùng là. Đống fibonacci cuối cùng

Giảm khóa và xóa nút

Đây là những thao tác quan trọng nhất được thảo luận trong Thao tác giảm khóa và Xóa nút.

Ví dụ về Python, Java và C / C ++

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.

thú vị bài viết...