C++ Programming Code Examples C++ > Data Structures Code Examples Program to Implement Fibonacci Heap Program to Implement Fibonacci Heap #include <iostream> #include <cmath> #include <cstdlib> using namespace std; /* Node Declaration */ struct node { int n; int degree; node* parent; node* child; node* left; node* right; char mark; char C; }; /* Class Declaration */ 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 < H->n) H = x; } else { H = x; } nH = nH + 1; return H; } /* Link Nodes in Fibonnaci Heap */ 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 < (z->child)->n) z->child = y; z->degree++; } /* Union Nodes in Fibonnaci Heap */ 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 Fibonnaci Heap */ int FibonacciHeap::Display(node* H) { node* p = H; if (p == NULL) { cout<<"The Heap is Empty"<<endl; return 0; } cout<<"The root nodes of Heap are: "<<endl; do { cout<<p->n; p = p->right; if (p != H) { cout<<"-->"; } } while (p != H && p->right != NULL); cout<<endl; } /* Extract Min Node in Fibonnaci Heap */ node* FibonacciHeap::Extract_Min(node* H1) { node* p; node* ptr; node* z = H1; p = z; ptr = z; if (z == NULL) return z; node* x; node* np; x = NULL; if (z->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 < H1->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; } /* Consolidate Node in Fibonnaci Heap */ int FibonacciHeap::Consolidate(node* H1) { int d, i; float f = (log(nH)) / (log(2)); int D = f; node* A[D]; for (i = 0; i <= D; i++) A[i] = NULL; node* x = H1; node* y; node* np; node* pt = x; do { pt = pt->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 <= D; j++) { if (A[j] != NULL) { A[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 < H->n) H = A[j]; } else { H = A[j]; } if(H == NULL) H = A[j]; else if (A[j]->n < H->n) H = A[j]; } } } /* Decrease key of Nodes in Fibonnaci Heap */ 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"<<endl; return 1; } if (ptr->n < k) { cout<<"Entered key greater than current key"<<endl; return 0; } ptr->n = k; y = ptr->parent; if (y != NULL && ptr->n < y->n) { Cut(H1, ptr, y); Cascase_cut(H1, y); } if (ptr->n < H->n) H = ptr; return 0; } /* Cut Nodes in Fibonnaci Heap */ 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 Cutting in Fibonnaci Heap */ 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); } } } /* Find Nodes in Fibonnaci Heap */ 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; } /* Delete Nodes in Fibonnaci Heap */ 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; } /* Main Contains Menu */ int main() { int n, m, l; FibonacciHeap fh; node* p; node* H; H = fh.InitializeHeap(); while (1) { cout<<"----------------------------"<<endl; cout<<"Operations on Binomial heap"<<endl; cout<<"----------------------------"<<endl; cout<<"1)Insert Element in the heap"<<endl; cout<<"2)Extract Minimum key node"<<endl; cout<<"3)Decrease key of a node"<<endl; cout<<"4)Delete a node"<<endl; cout<<"5)Display Heap"<<endl; cout<<"6)Exit"<<endl; cout<<"Enter Your Choice: "; cin>>l; switch(l) { case 1: cout<<"Enter the element to be inserted: "; cin>>m; p = fh.Create_node(m); H = fh.Insert(H, p); break; case 2: p = fh.Extract_Min(H); if (p != NULL) cout<<"The node with minimum key: "<<p->n<<endl; else cout<<"Heap is empty"<<endl; break; case 3: cout<<"Enter the key to be decreased: "; cin>>m; cout<<"Enter new key value: "; cin>>l; fh.Decrease_key(H, m, l); break; case 4: cout<<"Enter the key to be deleted: "; cin>>m; fh.Delete_key(H, m); break; case 5: cout<<"The Heap is: "<<endl; fh.Display(H); break; case 6: exit(1); default: cout<<"Wrong Choice"<<endl; } } return 0; }
