// C++ program for implementation of // Binomial Heap and Operations on it #include    using namespace std; // Structure of Node struct 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 Node 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 Node* 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 & h2 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 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 void 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 value Node* 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 element 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 void 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 element Node* 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 code int 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; } 

import java.util.ArrayList; import java.util.List; // Structure of Node class Node {  int val degree;  Node parent child sibling; } // Class to represent a Binomial Heap class 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);  } } 

# python program for implementation of # Binomial Heap and Operations on it INT_MIN = -2147483648; g = 0 # Structure of Node class 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 Node def 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 Trees def 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 & h2 def 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 Node def 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 Nodes def display(h): global g while (h): if g != 1 or h.val != 10: print(h.valend = ' '); 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 value def 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 element def 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_val def 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 element def 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 global binomialHeapInsert(10); binomialHeapInsert(20); binomialHeapInsert(30); binomialHeapInsert(40); binomialHeapInsert(50); print('The heap is:'); display(root); #Delete a particular element from heap root = binomialHeapDelete(root 10); print('nAfter deleting 10 the heap is:'); # stores bool  g = 1 # display display(root); #The code is contributed by Nidhi goel.  

using System; class BinomialHeap {  class Node {  public int val degree;  public Node parent child sibling;  }  static Node root = null;  static int BinomialLink(Node h1 Node h2)  {  h1.parent = h2;  h1.sibling = h2.child;  h2.child = h1;  h2.degree = h2.degree + 1;  return 0;  }  static Node CreateNode(int n)  {  Node newNode = new Node();  newNode.val = n;  newNode.parent = null;  newNode.sibling = null;  newNode.child = null;  newNode.degree = 0;  return newNode;  }  static Node MergeBHeaps(Node h1 Node h2)  {  if (h1 == null)  return h2;  if (h2 == null)  return h1;  Node res = null;  if (h1.degree <= h2.degree)  res = h1;  else if (h1.degree > h2.degree)  res = h2;  while (h1 != null && h2 != null) {  if (h1.degree < h2.degree)  h1 = h1.sibling;  else if (h1.degree == h2.degree) {  Node sib = h1.sibling;  h1.sibling = h2;  h1 = sib;  }  else {  Node sib = h2.sibling;  h2.sibling = h1;  h2 = sib;  }  }  return res;  }  static Node UnionBHeaps(Node h1 Node h2)  {  if (h1 == null && h2 == null)  return null;  Node res = MergeBHeaps(h1 h2);  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;  }  static void BinomialHeapInsert(int x)  {  root = UnionBHeaps(root CreateNode(x));  }  static void Display(Node h)  {  while (h != null) {  Console.Write(h.val + ' ');  Display(h.child);  h = h.sibling;  }  }  static int RevertList(Node h)  {  if (h.sibling != null) {  RevertList(h.sibling);  (h.sibling).sibling = h;  }  else  root = h;  return 0;  }  static Node ExtractMinBHeap(Node h)  {  if (h == null)  return null;  Node minNodePrev = null;  Node minNode = h;  int min = h.val;  Node curr = h;  while (curr.sibling != null) {  if ((curr.sibling).val < min) {  min = (curr.sibling).val;  minNodePrev = curr;  minNode = curr.sibling;  }  curr = curr.sibling;  }  if (minNodePrev == null && minNode.sibling == null)  h = null;  else if (minNodePrev == null)  h = minNode.sibling;  else  minNodePrev.sibling = minNode.sibling;  if (minNode.child != null) {  RevertList(minNode.child);  (minNode.child).sibling = null;  }  else  root = null;  // Delete minNode to avoid memory leak  minNode = null;  return UnionBHeaps(h root);  }  static Node FindNode(Node h int val)  {  if (h == null)  return null;  if (h.val == val)  return h;  Node res = FindNode(h.child val);  if (res != null)  return res;  return FindNode(h.sibling val);  }  static void DecreaseKeyBHeap(Node H int oldVal  int newVal)  {  Node node = FindNode(H oldVal);  if (node == null)  return;  node.val = newVal;  Node parent = node.parent;  while (parent != null && node.val < parent.val) {  Swap(ref node.val ref parent.val);  node = parent;  parent = parent.parent;  }  }  static Node BinomialHeapDelete(Node h int val)  {  if (h == null)  return null;  DecreaseKeyBHeap(h val int.MinValue);  return ExtractMinBHeap(h);  }  static void Swap(ref int a ref int b)  {  int temp = a;  a = b;  b = temp;  }  static void Main()  {  BinomialHeapInsert(10);  BinomialHeapInsert(20);  BinomialHeapInsert(30);  BinomialHeapInsert(40);  BinomialHeapInsert(50);  Console.WriteLine('The heap is:');  Display(root);  root = BinomialHeapDelete(root 10);  Console.WriteLine(  'nAfter deleting 10 the heap is:');  Display(root);  } } 

// javascript program for implementation of // Binomial Heap and Operations on it const INT_MIN = -2147483648; // Structure of Node class 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 Node function 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 Trees function 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 & h2 function 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 Node function binomialHeapInsert(x) {  // Create a new node and do union of  // this node with root  root = unionBHeaps(root createNode(x)); } // Function to display the Nodes function 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 value function 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 element function 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_val function 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 element function 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 global binomialHeapInsert(10); binomialHeapInsert(20); binomialHeapInsert(30); binomialHeapInsert(40); binomialHeapInsert(50); console.log('The heap is:'); display(root); // Delete a particular element from heap root = binomialHeapDelete(root 10); console.log('nAfter deleting 10 the heap is:'); display(root); //The code is contributed by Nidhi goel.