In previous post i.e. Set 1 we have discussed that implements these below functions:
- insert(H, k): Inserts a key ‘k’ to Binomial Heap ‘H’. This operation first creates a Binomial Heap with single key ‘k’, then calls union on H and the new Binomial heap.
- getMin(H): A simple way to getMin() is to traverse the list of root of Binomial Trees and return the minimum key. This implementation requires O(Logn) time. It can be optimized to O(1) by maintaining a pointer to minimum key root.
- extractMin(H): This operation also uses union(). We first call getMin() to find the minimum key Binomial Tree, then we remove the node and create a new Binomial Heap by connecting all subtrees of the removed minimum node. Finally we call union() on H and the newly created Binomial Heap. This operation requires O(Logn) time.
Examples:
12------------10--------------------20
/ \ / | \
15 50 70 50 40
| / | |
30 80 85 65
|
100
A Binomial Heap with 13 nodes. It is a collection of 3
Binomial Trees of orders 0, 2 and 3 from left to right.
10--------------------20
/ \ / | \
15 50 70 50 40
| / | |
30 80 85 65
|
100
In this post, below functions are implemented.
- delete(H): Like Binary Heap, delete operation first reduces the key to minus infinite, then calls extractMin().
- decreaseKey(H): decreaseKey() is also similar to Binary Heap. We compare the decreases key with it parent and if parent’s key is more, we swap keys and recur for parent. We stop when we either reach a node whose parent has smaller key or we hit the root node. Time complexity of decreaseKey() is O(Logn)
Implementation:
C++
// C++ program for implementation of// Binomial Heap and Operations on it#include <bits/stdc++.h>using namespace std;// Structure of Nodestruct Node { int val, degree; Node *parent, *child, *sibling;};// Making root global to avoid one extra// parameter in all functions.Node* root = NULL;// link two heaps by making h1 a child// of h2.int binomialLink(Node* h1, Node* h2){ h1->parent = h2; h1->sibling = h2->child; h2->child = h1; h2->degree = h2->degree + 1;}// create a NodeNode* createNode(int n){ Node* new_node = new Node; new_node->val = n; new_node->parent = NULL; new_node->sibling = NULL; new_node->child = NULL; new_node->degree = 0; return new_node;}// This function merge two Binomial TreesNode* mergeBHeaps(Node* h1, Node* h2){ if (h1 == NULL) return h2; if (h2 == NULL) return h1; // define a Node Node* res = NULL; // check degree of both Node i.e. // which is greater or smaller if (h1->degree <= h2->degree) res = h1; else if (h1->degree > h2->degree) res = h2; // traverse till if any of heap gets empty while (h1 != NULL && h2 != NULL) { // if degree of h1 is smaller, increment h1 if (h1->degree < h2->degree) h1 = h1->sibling; // Link h1 with h2 in case of equal degree else if (h1->degree == h2->degree) { Node* sib = h1->sibling; h1->sibling = h2; h1 = sib; } // if h2 is greater else { Node* sib = h2->sibling; h2->sibling = h1; h2 = sib; } } return res;}// This function perform union operation on two// binomial heap i.e. h1 & h2Node* unionBHeaps(Node* h1, Node* h2){ if (h1 == NULL && h2 == NULL) return NULL; Node* res = mergeBHeaps(h1, h2); // Traverse the merged list and set // values according to the degree of // Nodes Node *prev = NULL, *curr = res, *next = curr->sibling; while (next != NULL) { if ((curr->degree != next->degree) || ((next->sibling != NULL) && (next->sibling)->degree == curr->degree)) { prev = curr; curr = next; } else { if (curr->val <= next->val) { curr->sibling = next->sibling; binomialLink(next, curr); } else { if (prev == NULL) res = next; else prev->sibling = next; binomialLink(curr, next); curr = next; } } next = curr->sibling; } return res;}// Function to insert a Nodevoid binomialHeapInsert(int x){ // Create a new node and do union of // this node with root root = unionBHeaps(root, createNode(x));}// Function to display the Nodesvoid display(Node* h){ while (h) { cout << h->val << " "; display(h->child); h = h->sibling; }}// Function to reverse a list// using recursion.int revertList(Node* h){ if (h->sibling != NULL) { revertList(h->sibling); (h->sibling)->sibling = h; } else root = h;}// Function to extract minimum valueNode* extractMinBHeap(Node* h){ if (h == NULL) return NULL; Node* min_node_prev = NULL; Node* min_node = h; // Find minimum value int min = h->val; Node* curr = h; while (curr->sibling != NULL) { if ((curr->sibling)->val < min) { min = (curr->sibling)->val; min_node_prev = curr; min_node = curr->sibling; } curr = curr->sibling; } // If there is a single Node if (min_node_prev == NULL && min_node->sibling == NULL) h = NULL; else if (min_node_prev == NULL) h = min_node->sibling; // Remove min node from list else min_node_prev->sibling = min_node->sibling; // Set root (which is global) as children // list of min node if (min_node->child != NULL) { revertList(min_node->child); (min_node->child)->sibling = NULL; } else root = NULL; delete min_node; // Do union of root h and children return unionBHeaps(h, root);}// Function to search for an elementNode* findNode(Node* h, int val){ if (h == NULL) return NULL; // check if key is equal to the root's data if (h->val == val) return h; // Recur for child Node* res = findNode(h->child, val); if (res != NULL) return res; return findNode(h->sibling, val);}// Function to decrease the value of old_val// to new_valvoid decreaseKeyBHeap(Node* H, int old_val, int new_val){ // First check element present or not Node* node = findNode(H, old_val); // return if Node is not present if (node == NULL) return; // Reduce the value to the minimum node->val = new_val; Node* parent = node->parent; // Update the heap according to reduced value while (parent != NULL && node->val < parent->val) { swap(node->val, parent->val); node = parent; parent = parent->parent; }}// Function to delete an elementNode* binomialHeapDelete(Node* h, int val){ // Check if heap is empty or not if (h == NULL) return NULL; // Reduce the value of element to minimum decreaseKeyBHeap(h, val, INT_MIN); // Delete the minimum element from heap return extractMinBHeap(h);}// Driver codeint main(){ // Note that root is global binomialHeapInsert(10); binomialHeapInsert(20); binomialHeapInsert(30); binomialHeapInsert(40); binomialHeapInsert(50); cout << "The heap is:\n"; display(root); // Delete a particular element from heap root = binomialHeapDelete(root, 10); cout << "\nAfter deleting 10, the heap is:\n"; display(root); return 0;} |
Java
import java.util.ArrayList;import java.util.List;// Structure of Nodeclass Node { int val, degree; Node parent, child, sibling;}// Class to represent a Binomial Heapclass BinomialHeap { private Node root; // Making root global to avoid one extra parameter in all functions. public BinomialHeap() { this.root = null; } // Link two heaps by making h1 a child of h2. private void binomialLink(Node h1, Node h2) { h1.parent = h2; h1.sibling = h2.child; h2.child = h1; h2.degree = h2.degree + 1; } // Create a Node private Node createNode(int n) { Node new_node = new Node(); new_node.val = n; new_node.parent = null; new_node.sibling = null; new_node.child = null; new_node.degree = 0; return new_node; } // This function merge two Binomial Trees private Node mergeBHeaps(Node h1, Node h2) { if (h1 == null) return h2; if (h2 == null) return h1; // Define a Node Node res; // Check degree of both Node i.e. which is greater or smaller if (h1.degree <= h2.degree) res = h1; else res = h2; // Traverse till if any of the heap gets empty while (h1 != null && h2 != null) { // If degree of h1 is smaller, increment h1 if (h1.degree < h2.degree) h1 = h1.sibling; // Link h1 with h2 in case of equal degree else if (h1.degree == h2.degree) { Node sib = h1.sibling; h1.sibling = h2; h1 = sib; } // If h2 is greater else { Node sib = h2.sibling; h2.sibling = h1; h2 = sib; } } return res; } // This function performs the union operation on two binomial heaps i.e. h1 & h2 private Node unionBHeaps(Node h1, Node h2) { if (h1 == null && h2 == null) return null; Node res = mergeBHeaps(h1, h2); // Traverse the merged list and set values according to the degree of Nodes Node prev = null, curr = res, next = curr.sibling; while (next != null) { if ((curr.degree != next.degree) || ((next.sibling != null) && (next.sibling).degree == curr.degree)) { prev = curr; curr = next; } else { if (curr.val <= next.val) { curr.sibling = next.sibling; binomialLink(next, curr); } else { if (prev == null) res = next; else prev.sibling = next; binomialLink(curr, next); curr = next; } } next = curr.sibling; } return res; } // Function to insert a Node public void binomialHeapInsert(int x) { // Create a new node and do union of this node with root root = unionBHeaps(root, createNode(x)); } // Function to display the Nodes private void display(Node h) { while (h != null) { System.out.print(h.val + " "); display(h.child); h = h.sibling; } } // Function to reverse a list using recursion. private Node revertList(Node h) { if (h.sibling != null) { revertList(h.sibling); (h.sibling).sibling = h; } else root = h; return root; } // Function to extract the minimum value private Node extractMinBHeap(Node h) { if (h == null) return null; Node min_node_prev = null; Node min_node = h; // Find the minimum value int min = h.val; Node curr = h; while (curr.sibling != null) { if ((curr.sibling).val < min) { min = (curr.sibling).val; min_node_prev = curr; min_node = curr.sibling; } curr = curr.sibling; } // If there is a single Node if (min_node_prev == null && min_node.sibling == null) h = null; else if (min_node_prev == null) h = min_node.sibling; // Remove the min node from the list else min_node_prev.sibling = min_node.sibling; // Set root (which is global) as children list of min node if (min_node.child != null) { revertList(min_node.child); (min_node.child).sibling = null; } else root = null; return unionBHeaps(h, root); } // Function to search for an element private Node findNode(Node h, int val) { if (h == null) return null; // Check if key is equal to the root's data if (h.val == val) return h; // Recur for child Node res = findNode(h.child, val); if (res != null) return res; return findNode(h.sibling, val); } // Function to decrease the value of old_val to new_val private void decreaseKeyBHeap(Node H, int old_val, int new_val) { // First check if the Node is present Node node = findNode(H, old_val); // Return if Node is not present if (node == null) return; // Reduce the value to the minimum node.val = new_val; Node parent = node.parent; // Update the heap according to the reduced value while (parent != null && node.val < parent.val) { int temp = node.val; node.val = parent.val; parent.val = temp; node = parent; parent = parent.parent; } } // Function to delete an element public void binomialHeapDelete(int val) { // Check if the heap is empty or not if (root == null) return; // Reduce the value of element to minimum decreaseKeyBHeap(root, val, Integer.MIN_VALUE); // Delete the minimum element from the heap root = extractMinBHeap(root); } // Driver code public static void main(String[] args) { BinomialHeap heap = new BinomialHeap(); heap.binomialHeapInsert(10); heap.binomialHeapInsert(20); heap.binomialHeapInsert(30); heap.binomialHeapInsert(40); heap.binomialHeapInsert(50); System.out.println("The heap is:"); heap.display(heap.root); // Delete a particular element from the heap heap.binomialHeapDelete(10); System.out.println("\nAfter deleting 10, the heap is:"); heap.display(heap.root); }} |
Python3
# python program for implementation of# Binomial Heap and Operations on itINT_MIN = -2147483648;g = 0# Structure of Nodeclass Node: def __init__(self): self.val = 0; self.degree = 0; self.parent = None; self.child = None; self.sibling = None;# Making root global to avoid one extra# parameter in all functions.root = None;# link two heaps by making h1 a child# of h2.def binomialLink(h1, h2): h1.parent = h2; h1.sibling = h2.child; h2.child = h1; h2.degree = h2.degree + 1; return -1;# create a Nodedef createNode(n): new_node = Node(); new_node.val = n; new_node.parent = None; new_node.sibling = None; new_node.child = None; new_node.degree = 0; return new_node;# This function merge two Binomial Treesdef mergeBHeaps(h1, h2): if (h1 == None): return h2; if (h2 == None): return h1; # define a Node res = None; # check degree of both Node i.e. # which is greater or smaller if (h1.degree <= h2.degree): res = h1; elif(h1.degree > h2.degree): res = h2; # traverse till if any of heap gets empty while (h1 != None and h2 != None): # if degree of h1 is smaller, increment h1 if (h1.degree < h2.degree): h1 = h1.sibling; # Link h1 with h2 in case of equal degree elif(h1.degree == h2.degree): sib = h1.sibling; h1.sibling = h2; h1 = sib; # if h2 is greater else: sib = h2.sibling; h2.sibling = h1; h2 = sib; return res;# This function perform union operation on two# binomial heap i.e. h1 & h2def unionBHeaps(h1, h2): # global root if (h1 == None and h2 == None): return None; res = mergeBHeaps(h1, h2); # Traverse the merged list and set # values according to the degree of # Nodes prev = None; curr = res; next = curr.sibling; while (next != None): if ((curr.degree != next.degree) or ((next.sibling != None) and (next.sibling).degree == curr.degree)): prev = curr; curr = next; else: if (curr.val <= next.val): curr.sibling = next.sibling; binomialLink(next, curr); else: if (prev == None): res = next; else: prev.sibling = next; binomialLink(curr, next); curr = next; next = curr.sibling; return res;# Function to insert a Nodedef binomialHeapInsert(x): # Create a new node and do union of # this node with root global root root = unionBHeaps(root, createNode(x)); # Function to display the Nodesdef display(h): global g while (h): if g != 1 or h.val != 10: print(h.val,end = " "); display(h.child); h = h.sibling;# Function to reverse a list# using recursion.def revertList(h): if (h.sibling != None): revertList(h.sibling); (h.sibling).sibling = h; else: root = h; return -1;# Function to extract minimum valuedef extractMinBHeap(h): global root if (h == None): return None; min_node_prev = None; min_node = h; # Find minimum value min = h.val; curr = h; while (curr.sibling != None): if ((curr.sibling).val < min): min = (curr.sibling).val; min_node_prev = curr; min_node = curr.sibling; curr = curr.sibling; # If there is a single Node if (min_node_prev == None and min_node.sibling == None): h = None; elif(min_node_prev == None): h = min_node.sibling; # Remove min node from list else: min_node_prev.sibling = min_node.sibling; # Set root (which is global) as children # list of min node if (min_node.child != None): revertList(min_node.child); (min_node.child).sibling = None; else: root = None; del min_node; # Do union of root h and children return unionBHeaps(h, root);# Function to search for an elementdef findNode( h, val): if (h == None): return None; # check if key is equal to the root's data if (h.val == val): return h; # Recur for child res = findNode(h.child, val); if (res != None): return res; return findNode(h.sibling, val);# Function to decrease the value of old_val# to new_valdef decreaseKeyBHeap(H, old_val, new_val): # First check element present or not node = findNode(H, old_val); # return if Node is not present if (node == None): return; # Reduce the value to the minimum node.val = new_val; parent = node.parent; # Update the heap according to reduced value while (parent != None and node.val < parent.val): temp = node.val; node.val = parent.val; parent.val = temp; node = parent; parent = parent.parent;# Function to delete an elementdef binomialHeapDelete( h, val): global root; return root; # Check if heap is empty or not if (h == None): return None; # Reduce the value of element to minimum decreaseKeyBHeap(h, val, INT_MIN); # Delete the minimum element from heap return extractMinBHeap(h);#Driver code#Note that root is globalbinomialHeapInsert(10);binomialHeapInsert(20);binomialHeapInsert(30);binomialHeapInsert(40);binomialHeapInsert(50);print("The heap is:");display(root);#Delete a particular element from heaproot = binomialHeapDelete(root, 10);print("\nAfter deleting 10, the heap is:");# stores bool g = 1# displaydisplay(root);#The code is contributed by Nidhi goel. |
Javascript
// javascript program for implementation of// Binomial Heap and Operations on itconst INT_MIN = -2147483648;// Structure of Nodeclass Node { constructor(){ this.val = 0; this.degree = 0; this.parent = null; this.child = null; this.sibling = null; }}// Making root global to avoid one extra// parameter in all functions.let root = null;// link two heaps by making h1 a child// of h2.function binomialLink(h1, h2){ h1.parent = h2; h1.sibling = h2.child; h2.child = h1; h2.degree = h2.degree + 1; return -1;}// create a Nodefunction createNode(n){ let new_node = new Node; new_node.val = n; new_node.parent = null; new_node.sibling = null; new_node.child = null; new_node.degree = 0; return new_node;}// This function merge two Binomial Treesfunction mergeBHeaps(h1, h2){ if (h1 == null) return h2; if (h2 == null) return h1; // define a Node let res = null; // check degree of both Node i.e. // which is greater or smaller if (h1.degree <= h2.degree) res = h1; else if (h1.degree > h2.degree) res = h2; // traverse till if any of heap gets empty while (h1 != null && h2 != null) { // if degree of h1 is smaller, increment h1 if (h1.degree < h2.degree) h1 = h1.sibling; // Link h1 with h2 in case of equal degree else if (h1.degree == h2.degree) { let sib = h1.sibling; h1.sibling = h2; h1 = sib; } // if h2 is greater else { let sib = h2.sibling; h2.sibling = h1; h2 = sib; } } return res;}// This function perform union operation on two// binomial heap i.e. h1 & h2function unionBHeaps(h1, h2){ if (h1 == null && h2 == null) return null; let res = mergeBHeaps(h1, h2); // Traverse the merged list and set // values according to the degree of // Nodes let prev = null; let curr = res; let next = curr.sibling; while (next != null) { if ((curr.degree != next.degree) || ((next.sibling != null) && (next.sibling).degree == curr.degree)) { prev = curr; curr = next; } else { if (curr.val <= next.val) { curr.sibling = next.sibling; binomialLink(next, curr); } else { if (prev == null) res = next; else prev.sibling = next; binomialLink(curr, next); curr = next; } } next = curr.sibling; } return res;}// Function to insert a Nodefunction binomialHeapInsert(x){ // Create a new node and do union of // this node with root root = unionBHeaps(root, createNode(x));}// Function to display the Nodesfunction display(h){ while (h) { process.stdout.write(h.val + " "); display(h.child); h = h.sibling; }}// Function to reverse a list// using recursion.function revertList(h){ if (h.sibling != null) { revertList(h.sibling); (h.sibling).sibling = h; } else root = h; return -1;}// Function to extract minimum valuefunction extractMinBHeap(h){ if (h == null) return null; let min_node_prev = null; let min_node = h; // Find minimum value let min = h.val; let curr = h; while (curr.sibling != null) { if ((curr.sibling).val < min) { min = (curr.sibling).val; min_node_prev = curr; min_node = curr.sibling; } curr = curr.sibling; } // If there is a single Node if (min_node_prev == null && min_node.sibling == null) h = null; else if (min_node_prev == null) h = min_node.sibling; // Remove min node from list else min_node_prev.sibling = min_node.sibling; // Set root (which is global) as children // list of min node if (min_node.child != null) { revertList(min_node.child); (min_node.child).sibling = null; } else root = null; delete min_node; // Do union of root h and children return unionBHeaps(h, root);}// Function to search for an elementfunction findNode( h, val){ if (h == null) return null; // check if key is equal to the root's data if (h.val == val) return h; // Recur for child let res = findNode(h.child, val); if (res != null) return res; return findNode(h.sibling, val);}// Function to decrease the value of old_val// to new_valfunction decreaseKeyBHeap(H, old_val, new_val){ // First check element present or not let node = findNode(H, old_val); // return if Node is not present if (node == null) return; // Reduce the value to the minimum node.val = new_val; let parent = node.parent; // Update the heap according to reduced value while (parent != null && node.val < parent.val) { let temp = node.val; node.val = parent.val; parent.val = temp; node = parent; parent = parent.parent; }}// Function to delete an elementfunction binomialHeapDelete( h, val){ // Check if heap is empty or not if (h == null) return null; // Reduce the value of element to minimum decreaseKeyBHeap(h, val, INT_MIN); // Delete the minimum element from heap return extractMinBHeap(h);}// Driver code// Note that root is globalbinomialHeapInsert(10);binomialHeapInsert(20);binomialHeapInsert(30);binomialHeapInsert(40);binomialHeapInsert(50);console.log("The heap is:");display(root);// Delete a particular element from heaproot = binomialHeapDelete(root, 10);console.log("\nAfter deleting 10, the heap is:");display(root);//The code is contributed by Nidhi goel. |
Output
The heap is: 50 10 30 40 20 After deleting 10, the heap is: 20 30 40 50
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
