C++ Programming Code Examples C++ > Data Structures Code Examples C++ Program to Implement Binomial Heap C++ Program to Implement Binomial Heap #include <iostream> #include <cstdlib> using namespace std; /* Node Declaration */ struct node { int n; int degree; node* parent; node* child; node* sibling; }; /* Class Declaration */ class BinomialHeap { private: node *H; node *Hr; int count; public: node* Initializeheap(); int Binomial_link(node*, node*); node* Create_node(int); node* Union(node*, node*); node* Insert(node*, node*); node* Merge(node*, node*); node* Extract_Min(node*); int Revert_list(node*); int Display(node*); node* Search(node*, int); int Decrease_key(node*, int, int); int Delete(node*, int); BinomialHeap() { H = Initializeheap(); Hr = Initializeheap(); int count = 1; } }; /* Initialize Heap */ node* BinomialHeap::Initializeheap() { node* np; np = NULL; return np; } /* Linking nodes in Binomial Heap */ int BinomialHeap::Binomial_link(node* y, node* z) { y->parent = z; y->sibling = z->child; z->child = y; z->degree = z->degree + 1; } /* Create Nodes in Binomial Heap */ node* BinomialHeap::Create_node(int k) { node* p = new node; p->n = k; return p; } /* Insert Nodes in Binomial Heap */ node* BinomialHeap::Insert(node* H, node* x) { node* H1 = Initializeheap(); x->parent = NULL; x->child = NULL; x->sibling = NULL; x->degree = 0; H1 = x; H = Union(H, H1); return H; } /* Union Nodes in Binomial Heap */ node* BinomialHeap::Union(node* H1, node* H2) { node *H = Initializeheap(); H = Merge(H1, H2); if (H == NULL) return H; node* prev_x; node* next_x; node* x; prev_x = NULL; x = H; next_x = x->sibling; while (next_x != NULL) { if ((x->degree != next_x->degree) || ((next_x->sibling != NULL) && (next_x->sibling)->degree == x->degree)) { prev_x = x; x = next_x; } else { if (x->n <= next_x->n) { x->sibling = next_x->sibling; Binomial_link(next_x, x); } else { if (prev_x == NULL) H = next_x; else prev_x->sibling = next_x; Binomial_link(x, next_x); x = next_x; } } next_x = x->sibling; } return H; } /* Merge Nodes in Binomial Heap */ node* BinomialHeap::Merge(node* H1, node* H2) { node* H = Initializeheap(); node* y; node* z; node* a; node* b; y = H1; z = H2; if (y != NULL) { if (z != NULL) { if (y->degree <= z->degree) H = y; else if (y->degree > z->degree) H = z; } else H = y; } else H = z; while (y != NULL && z != NULL) { if (y->degree < z->degree) { y = y->sibling; } else if (y->degree == z->degree) { a = y->sibling; y->sibling = z; y = a; } else { b = z->sibling; z->sibling = y; z = b; } } return H; } /* Display Binomial Heap */ int BinomialHeap::Display(node* H) { if (H == NULL) { cout<<"The Heap is empty"<<endl; return 0; } cout<<"The root nodes are: "<<endl; node* p; p = H; while (p != NULL) { cout<<p->n; if (p->sibling != NULL) cout<<"-->"; p = p->sibling; } cout<<endl; } /* Extract Minimum */ node* BinomialHeap::Extract_Min(node* H1) { Hr = NULL; node* t = NULL; node* x = H1; if (x == NULL) { cout<<"Nothing to Extract"<<endl; return x; } int min = x->n; node* p = x; while (p->sibling != NULL) { if ((p->sibling)->n < min) { min = (p->sibling)->n; t = p; x = p->sibling; } p = p->sibling; } if (t == NULL && x->sibling == NULL) H1 = NULL; else if (t == NULL) H1 = x->sibling; else if (t->sibling == NULL) t = NULL; else t->sibling = x->sibling; if (x->child != NULL) { Revert_list(x->child); (x->child)->sibling = NULL; } H = Union(H1, Hr); return x; } /* Reverse List */ int BinomialHeap::Revert_list(node* y) { if (y->sibling != NULL) { Revert_list(y->sibling); (y->sibling)->sibling = y; } else { Hr = y; } } /* Search Nodes in Binomial Heap */ node* BinomialHeap::Search(node* H, int k) { node* x = H; node* p = NULL; if (x->n == k) { p = x; return p; } if (x->child != NULL && p == NULL) p = Search(x->child, k); if (x->sibling != NULL && p == NULL) p = Search(x->sibling, k); return p; } /* Decrease key of a node */ int BinomialHeap::Decrease_key(node* H, int i, int k) { int temp; node* p; node* y; node* z; p = Search(H, i); if (p == NULL) { cout<<"Invalid choice of key"<<endl; return 0; } if (k > p->n) { cout<<"Error!! New key is greater than current key"<<endl; return 0; } p->n = k; y = p; z = p->parent; while (z != NULL && y->n < z->n) { temp = y->n; y->n = z->n; z->n = temp; y = z; z = z->parent; } cout<<"Key reduced successfully"<<endl; } /* Delete Nodes in Binomial Heap */ int BinomialHeap::Delete(node* H, int k) { node* np; if (H == NULL) { cout<<"\nHEAP EMPTY!!!!!"; return 0; } Decrease_key(H, k, -1000); np = Extract_Min(H); if (np != NULL) cout<<"Node Deleted Successfully"<<endl; } /* Main Contains Menu */ int main() { int n, m, l, i; BinomialHeap bh; node* p; node *H; H = bh.Initializeheap(); char ch; 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 = bh.Create_node(m); H = bh.Insert(H, p); break; case 2: p = bh.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; bh.Decrease_key(H, m, l); break; case 4: cout<<"Enter the key to be deleted: "; cin>>m; bh.Delete(H, m); break; case 5: cout<<"The Heap is: "<<endl; bh.Display(H); break; case 6: exit(1); default: cout<<"Wrong Choice"; } } return 0; }
