Posted on by Kalkicode
Code Heap

# Binomial Heap Node deletion

Binomial Heap is a type of heap data structure that is used for efficiently implementing priority queues. It is similar to a binary heap but provides faster merging operations. One of the key operations in a binomial heap is node deletion, where the minimum (or maximum) node is removed. This article discusses the process of deleting a node from a binomial heap using the provided C code.

## Problem Statement

The problem is to implement the node deletion operation in a binomial heap efficiently. Binomial heaps consist of a collection of binomial trees, each of which follows certain rules and has a specific structure. Deleting the minimum node involves finding the tree with the smallest root value, removing it, and merging its children back into the main heap.

## Example

Let's consider a simple example of a binomial heap to illustrate the node deletion process.

Suppose we have the following binomial heap:

``````
21-------10 ----------- 1
|            / | \
|           /  |  \
12         3   4   7
/ \  |
/   \ |
5   9 11
|
|
6
``````

After deleting the minimum node (which is 1), the heap should look like this:

``````
7 ------------  3
|            /  |  \
|           /   |   \
21         4    5    9
/ \   |
/   \  |
10   11 6
|
|
12
``````

## Idea to Solve

The main idea to solve the problem of node deletion in a binomial heap is to follow these steps:

1. Find the tree with the minimum root value.
2. Remove this tree from the heap.
3. Merge its child trees back into the main heap.

## Algorithm

1. Find Minimum Tree

Iterate through the roots of all trees in the binomial heap and find the tree with the smallest root value. This tree will be the one to be removed.

2. Remove Minimum Tree

Once the minimum tree is identified, unlink it from the root list of the binomial heap.

3. Merge Child Trees

Iterate through the child trees of the minimum tree and add them back to the main heap. This involves merging them with existing trees of the same order. This is done using the `addSubTree` function.

4. Delete Minimum Node

Finally, delete the node of the minimum tree that was removed.

## Code Solution

``````// Include header file
#include <stdio.h>
#include <stdlib.h>

/*
C program
Binomial Heap Node deletion
*/
// Define TreeNode
struct TreeNode
{
int key;
int counter;
struct TreeNode *sibling;
struct TreeNode *parent;
struct TreeNode *child;
};
// Define BinomialHeap
struct BinomialHeap
{
struct TreeNode *root;
};
// Returns a new node of tree
struct TreeNode *newNode(int key, struct TreeNode *sibling)
{
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node != NULL)
{
node->key = key;
node->sibling = sibling;
// Set default value of node
node->child = NULL;
node->parent = NULL;
node->counter = 0;
}
else
{
printf("\n Memory Overflow to create tree node\n");
}
return node;
}
// This is provide new Binomial Heap Tree
struct BinomialHeap *newTree()
{
struct BinomialHeap *tree = (struct BinomialHeap *) malloc(sizeof(struct BinomialHeap));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("\n Memory Overflow to create new tree \n");
}
return tree;
}
// Determine that whether the given node and next sibling tree have same number of children nodes
int isCombine(struct TreeNode *node)
{
if (node != NULL && node->sibling != NULL && node->counter == node->sibling->counter)
{
return 1;
}
else
{
return 0;
}
}
// This is attack child tree into parent tree
struct TreeNode *changeRelation(struct TreeNode *parentNode, struct TreeNode *childNode)
{
if (parentNode->sibling == childNode)
{
parentNode->sibling = childNode->sibling;
}
childNode->sibling = parentNode->child;
parentNode->child = childNode;
childNode->parent = parentNode;
parentNode->counter += 1;
return parentNode;
}
// Recursively merging of two tree
struct TreeNode *merge(struct TreeNode *node1, struct TreeNode *node2)
{
struct TreeNode *temp = NULL;
if (node1->key < node2->key)
{
temp = changeRelation(node1, node2);
}
else
{
temp = changeRelation(node2, node1);
}
if (isCombine(temp) == 1)
{
temp = merge(temp, temp->sibling);
}
return temp;
}
// Handles the request of add new key into the tree
void insert(struct BinomialHeap *tree, int key)
{
// Create new node of tree
struct TreeNode *node = newNode(key, tree->root);
if (tree->root == NULL)
{
tree->root = node;
}
else if (isCombine(node) == 1)
{
// When need to combine two sibling
tree->root = merge(node, tree->root);
}
else
{
tree->root = node;
}
}
// This is sort add subtree
struct TreeNode *addSubTree(struct TreeNode *front, struct TreeNode *subtree)
{
if (front == NULL)
{
return subtree;
}
else if (subtree->counter > front->counter)
{
}
else
{
// Add subtree before front tree
subtree->sibling = front;
if (isCombine(subtree) == 1)
{
// Returns the  new result after added subtree
return merge(subtree, front);
}
else
{
return subtree;
}
}
}
// In-order view of Binomial Heap from left to right in top tree
void printTree(struct TreeNode *node)
{
if (node == NULL)
{
return;
}
printf("  %d", node->key);
// Visit of child and sibling nodes
printTree(node->child);
printTree(node->sibling);
}
// Return minimum key value of tree
int minimum(struct TreeNode *root)
{
if (root == NULL)
{
// When empty tree
return -1;
}
struct TreeNode *auxiliary = root;
int result = root->key;
// Find last node
while (auxiliary!= NULL)
{
if (result > auxiliary->key)
{
result = auxiliary->key;
}
auxiliary = auxiliary->sibling;
}
return result;
}
// This is handles request to delete minimum nodes of Binomial heap
void deleteMinKey(struct BinomialHeap *tree)
{
if (tree->root == NULL)
{
printf("\n Empty Tree \n");
return;
}
// Define some useful variables
struct TreeNode *node = NULL;
struct TreeNode *auxiliary = NULL;
struct TreeNode *small = tree->root;
// Starting to first tree
node = tree->root;
// Find min key subtree in top of Binomial heap
while (node->sibling != NULL)
{
if (node->sibling->key < small->key)
{
auxiliary = node;
small = node->sibling;
}
// Visits to next sibling
node = node->sibling;
}
if (auxiliary != NULL)
{
// Segregate the minimum key subtree
auxiliary->sibling = small->sibling;
}
else
{
// Delete first subtree
tree->root = small->sibling;
}
// Get the child of deleted min key node
node = small->child;
// Add the delete node child into actual tree
while (node != NULL)
{
auxiliary = node;
node = node->sibling;
//Set default value of subtree
auxiliary->sibling = NULL;
auxiliary->parent = NULL;
// Add subtree to actual tree
}
printf("\n After Delete small Node : %d \n", small->key);
// Delete minimum value key node
free(small);
small = NULL;
printTree(tree->root);
}
int main()
{
struct BinomialHeap *tree = newTree();
insert(tree, 6);
insert(tree, 5);
insert(tree, 9);
insert(tree, 3);
insert(tree, 4);
insert(tree, 11);
insert(tree, 1);
insert(tree, 7);
insert(tree, 12);
insert(tree, 10);
insert(tree, 21);
printf("\n Constructing Binomial Heap \n");
/*
Constructing of Binomial Heap
==========================
21-------10 ----------- 1
|            / | \
|           /  |  \
12         3   4   7
/ \  |
/   \ |
5   9 11
|
|
6
==========================
Logical view
*/
printTree(tree->root);
printf("\n Minimum node : %d ", minimum(tree->root));
deleteMinKey(tree);
/*
After Detete Min Node 1
==========================

7 ------------  3
|            /  |  \
|           /   |   \
21         4    5    9
/ \   |
/   \  |
10   11 6
|
|
12
==========================
Logical view
*/
deleteMinKey(tree);
/*
After Detete Min Node 3
==========================

9 ------------  4
/  |  \
/   |   \
5   10   11
/ \   |
/   \  |
7     6 12
|
|
21
==========================
Logical view
*/
deleteMinKey(tree);
/*
After Detete Min Node 4
==========================

5
/ | \
/  |  \
9   7   6
/ |   |
10  11  |
|       21
12

==========================
Logical view
*/
deleteMinKey(tree);
/*
After Detete Min Node 5
=========================

6 -------7 ----------- 9
|           / |
|          /  |
21        10  11
|
|
12
Logical view
*/
return 0;
}``````

#### Output

`````` Constructing Binomial Heap
21  10  12  1  3  5  6  9  4  11  7
Minimum node : 1
After Delete small Node : 1
7  21  3  4  10  12  11  5  6  9
After Delete small Node : 3
9  4  5  7  21  6  10  12  11
After Delete small Node : 4
5  9  10  12  11  7  21  6
After Delete small Node : 5
6  7  21  9  10  12  11``````
``````/*
Java program
Binomial Heap Node deletion
*/

// Define TreeNode
class TreeNode
{
public int key;
public int counter;
public TreeNode sibling;
public TreeNode parent;
public TreeNode child;
public TreeNode(int key,TreeNode sibling)
{
this.key = key;
this.sibling = sibling;
// Set default value of node
this.child = null;
this.parent = null;
this.counter = 0;
}

}
// Define BinomialHeap
public class BinomialHeap
{
public TreeNode root;
public BinomialHeap()
{
this.root = null;
}
// Determine that whether the given node and next sibling tree have same number of children nodes
public boolean isCombine(TreeNode node)
{
if (node != null && node.sibling != null && node.counter == node.sibling.counter)
{
return true;
}
else
{
return false;
}
}
// This is attack child tree into parent tree
public TreeNode changeRelation(TreeNode parentNode, TreeNode childNode)
{
if (parentNode.sibling == childNode)
{
parentNode.sibling = childNode.sibling;
}
childNode.sibling = parentNode.child;
parentNode.child = childNode;
childNode.parent = parentNode;
parentNode.counter += 1;
return parentNode;
}
// Recursively merging of two tree
public TreeNode merge(TreeNode node1, TreeNode node2)
{
TreeNode temp = null;
if (node1.key < node2.key)
{
temp = changeRelation(node1, node2);
}
else
{
temp = changeRelation(node2, node1);
}
if (isCombine(temp) == true)
{
temp = merge(temp, temp.sibling);
}
return temp;
}
// Handles the request of add new key into the tree
public void insert( int key)
{
// Create new node of tree
TreeNode node = new TreeNode(key, this.root);
if (this.root == null)
{
this.root = node;
}
else if (isCombine(node) == true)
{
// When need to combine two sibling
this.root = merge(node, this.root);
}
else
{
this.root = node;
}
}
// This is sort add subtree
public TreeNode addSubTree(TreeNode front, TreeNode subtree)
{
if (front == null)
{
return subtree;
}
else if (subtree.counter > front.counter)
{
return front;
}
else
{
// Add subtree before front tree
subtree.sibling = front;
if (isCombine(subtree) == true)
{
// Returns the  new result after added subtree
return merge(subtree, front);
}

return subtree;

}
}
// In-order view of Binomial Heap from left to right in top tree
public void printTree(TreeNode node)
{
if (node == null)
{
return;
}
System.out.print(" " + node.key );
// Visit of child and sibling nodes
printTree(node.child);
printTree(node.sibling);
}
// Return minimum key value of tree
public int minimum()
{
if (this.root == null)
{
// When empty tree
return -1;
}
TreeNode auxiliary = this.root;
int result = this.root.key;
// Find last node
while (auxiliary != null)
{
if (result > auxiliary.key)
{
result = auxiliary.key;
}
auxiliary = auxiliary.sibling;
}
return result;
}
// This is handles request to delete minimum nodes of Binomial heap
public void deleteMinKey()
{
if (this.root == null)
{
System.out.print("\n Empty Tree \n");
return;
}
// Define some useful variables
TreeNode node = null;
TreeNode auxiliary = null;
TreeNode small = this.root;
// Starting to first this
node = this.root;
// Find min key subtree in top of Binomial heap
while (node.sibling != null)
{
if (node.sibling.key < small.key)
{
auxiliary = node;
small = node.sibling;
}
// Visits to next sibling
node = node.sibling;
}
if (auxiliary != null)
{
// Segregate the minimum key subtree
auxiliary.sibling = small.sibling;
}
else
{
// Delete first subtree
this.root = small.sibling;
}
// Get the child of deleted min key node
node = small.child;
// Add the delete node child into actual tree
while (node != null)
{
auxiliary = node;
node = node.sibling;
//Set default value of subtree
auxiliary.sibling = null;
auxiliary.parent = null;
// Add subtree to actual tree
}
System.out.print("\n After Delete small Node : " + small.key + " \n");
// Delete minimum value key node
small = null;
printTree(this.root);
}
public static void main(String[] args)
{
BinomialHeap tree = new BinomialHeap();
tree.insert(6);
tree.insert( 5);
tree.insert( 9);
tree.insert( 3);
tree.insert( 4);
tree.insert( 11);
tree.insert( 1);
tree.insert( 7);
tree.insert( 12);
tree.insert( 10);
tree.insert( 21);
System.out.print("\n Constructing Binomial Heap \n");
/*
Constructing of Binomial Heap
==========================
21-------10 ----------- 1
|            / | \
|           /  |  \
12         3   4   7
/ \  |
/   \ |
5   9 11
|
|
6
==========================
Logical view
*/
tree.printTree(tree.root);
System.out.print("\n Minimum node : " + tree.minimum() + " ");
tree.deleteMinKey();
/*
After Detete Min Node 1
==========================

7 ------------  3
|            /  |  \
|           /   |   \
21         4    5    9
/ \   |
/   \  |
10   11 6
|
|
12
==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 3
==========================

9 ------------  4
/  |  \
/   |   \
5   10   11
/ \   |
/   \  |
7     6 12
|
|
21
==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 4
==========================

5
/ | \
/  |  \
9   7   6
/ |   |
10  11  |
|       21
12

==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 5
=========================

6 -------7 ----------- 9
|           / |
|          /  |
21        10  11
|
|
12
Logical view
*/
}
}``````

#### Output

`````` Constructing Binomial Heap
21 10 12 1 3 5 6 9 4 11 7
Minimum node : 1
After Delete small Node : 1
7 21 3 4 10 12 11 5 6 9
After Delete small Node : 3
9 4 5 7 21 6 10 12 11
After Delete small Node : 4
5 9 10 12 11 7 21 6
After Delete small Node : 5
6 7 21 9 10 12 11``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ program
Binomial Heap Node deletion
*/

//  Define TreeNode
class TreeNode
{
public:
int key;
int counter;
TreeNode *sibling;
TreeNode *parent;
TreeNode *child;
TreeNode(int key, TreeNode *sibling)
{
this->key = key;
this->sibling = sibling;
//  Set default value of node
this->child = NULL;
this->parent = NULL;
this->counter = 0;
}
};
//  Define BinomialHeap
class BinomialHeap
{
public:
TreeNode *root;
BinomialHeap()
{
this->root = NULL;
}
//  Determine that whether the given node and next sibling tree have same number of children nodes
bool isCombine(TreeNode *node)
{
if (node != NULL && node->sibling != NULL
&& node->counter == node->sibling->counter)
{
return true;
}
else
{
return false;
}
}
//  This is attack child tree into parent tree
TreeNode *changeRelation(TreeNode *parentNode, TreeNode *childNode)
{
if (parentNode->sibling == childNode)
{
parentNode->sibling = childNode->sibling;
}
childNode->sibling = parentNode->child;
parentNode->child = childNode;
childNode->parent = parentNode;
parentNode->counter += 1;
return parentNode;
}
//  Recursively merging of two tree
TreeNode *merge(TreeNode *node1, TreeNode *node2)
{
TreeNode *temp = NULL;
if (node1->key < node2->key)
{
temp = this->changeRelation(node1, node2);
}
else
{
temp = this->changeRelation(node2, node1);
}
if (this->isCombine(temp) == true)
{
temp = this->merge(temp, temp->sibling);
}
return temp;
}
//  Handles the request of add new key into the tree
void insert(int key)
{
//  Create new node of tree
TreeNode *node = new TreeNode(key, this->root);
if (this->root == NULL)
{
this->root = node;
}
else if (this->isCombine(node) == true)
{
//  When need to combine two sibling
this->root = this->merge(node, this->root);
}
else
{
this->root = node;
}
}
//  This is sort add subtree
{
if (front == NULL)
{
return subtree;
}
else if (subtree->counter > front->counter)
{
return front;
}
else
{
//  Add subtree before front tree
subtree->sibling = front;
if (this->isCombine(subtree) == true)
{
//  Returns the  new result after added subtree
return this->merge(subtree, front);
}
return subtree;
}
}
//  In-order view of Binomial Heap from left to right in top tree
void printTree(TreeNode *node)
{
if (node == NULL)
{
return;
}
cout << "  " << node->key;
//  Visit of child and sibling nodes
this->printTree(node->child);
this->printTree(node->sibling);
}
//  Return minimum key value of tree
int minimum()
{
if (this->root == NULL)
{
//  When empty tree
return -1;
}
TreeNode *auxiliary = this->root;
int result = this->root->key;
//  Find last node
while (auxiliary != NULL)
{
if (result > auxiliary->key)
{
result = auxiliary->key;
}
auxiliary = auxiliary->sibling;
}
return result;
}
//  This is handles request to delete minimum nodes of Binomial heap
void deleteMinKey()
{
if (this->root == NULL)
{
cout << "\n Empty Tree \n";
return;
}
//  Define some useful variables
TreeNode *node = NULL;
TreeNode *auxiliary = NULL;
TreeNode *small = this->root;
//  Starting to first this
node = this->root;
//  Find min key subtree in top of Binomial heap
while (node->sibling != NULL)
{
if (node->sibling->key < small->key)
{
auxiliary = node;
small = node->sibling;
}
//  Visits to next sibling
node = node->sibling;
}
if (auxiliary != NULL)
{
//  Segregate the minimum key subtree
auxiliary->sibling = small->sibling;
}
else
{
//  Delete first subtree
this->root = small->sibling;
}
//  Get the child of deleted min key node
node = small->child;
//  Add the delete node child into actual tree
while (node != NULL)
{
auxiliary = node;
node = node->sibling;
// Set default value of subtree
auxiliary->sibling = NULL;
auxiliary->parent = NULL;
//  Add subtree to actual tree
}
cout << "\n After Delete small Node : " << small->key << " \n";
//  Delete minimum value key node
small = NULL;
this->printTree(this->root);
}
};
int main()
{
BinomialHeap tree = BinomialHeap();
tree.insert(6);
tree.insert(5);
tree.insert(9);
tree.insert(3);
tree.insert(4);
tree.insert(11);
tree.insert(1);
tree.insert(7);
tree.insert(12);
tree.insert(10);
tree.insert(21);
cout << "\n Constructing Binomial Heap \n";
/*
Constructing of Binomial Heap
==========================
21-------10 ----------- 1
|            / | \
|           /  |  \
12         3   4   7
/ \  |
/   \ |
5   9 11
|
|
6
==========================
Logical view
*/
tree.printTree(tree.root);
cout << "\n Minimum node : " << tree.minimum() << " ";
tree.deleteMinKey();
/*
After Detete Min Node 1
==========================

7 ------------  3
|            /  |  \
|           /   |   \
21         4    5    9
/ \   |
/   \  |
10   11 6
|
|
12
==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 3
==========================

9 ------------  4
/  |  \
/   |   \
5   10   11
/ \   |
/   \  |
7     6 12
|
|
21
==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 4
==========================

5
/ | \
/  |  \
9   7   6
/ |   |
10  11  |
|       21
12

==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 5
=========================

6 -------7 ----------- 9
|           / |
|          /  |
21        10  11
|
|
12
Logical view
*/
cout << "\n";
return 0;
}``````

#### Output

`````` Constructing Binomial Heap
21  10  12  1  3  5  6  9  4  11  7
Minimum node : 1
After Delete small Node : 1
7  21  3  4  10  12  11  5  6  9
After Delete small Node : 3
9  4  5  7  21  6  10  12  11
After Delete small Node : 4
5  9  10  12  11  7  21  6
After Delete small Node : 5
6  7  21  9  10  12  11``````
``````// Include namespace system
using System;
/*
C# program
Binomial Heap Node deletion
*/
//  Define TreeNode
public class TreeNode
{
public int key;
public int counter;
public TreeNode sibling;
public TreeNode parent;
public TreeNode child;
public TreeNode(int key, TreeNode sibling)
{
this.key = key;
this.sibling = sibling;
//  Set default value of node
this.child = null;
this.parent = null;
this.counter = 0;
}
}
//  Define BinomialHeap
public class BinomialHeap
{
public TreeNode root;
public BinomialHeap()
{
this.root = null;
}
//  Determine that whether the given node and next sibling tree have same number of children nodes
public Boolean isCombine(TreeNode node)
{
if (node != null && node.sibling != null && node.counter == node.sibling.counter)
{
return true;
}
else
{
return false;
}
}
//  This is attack child tree into parent tree
public TreeNode changeRelation(TreeNode parentNode, TreeNode childNode)
{
if (parentNode.sibling == childNode)
{
parentNode.sibling = childNode.sibling;
}
childNode.sibling = parentNode.child;
parentNode.child = childNode;
childNode.parent = parentNode;
parentNode.counter += 1;
return parentNode;
}
//  Recursively merging of two tree
public TreeNode merge(TreeNode node1, TreeNode node2)
{
TreeNode temp = null;
if (node1.key < node2.key)
{
temp = changeRelation(node1, node2);
}
else
{
temp = changeRelation(node2, node1);
}
if (isCombine(temp) == true)
{
temp = merge(temp, temp.sibling);
}
return temp;
}
//  Handles the request of add new key into the tree
public void insert(int key)
{
//  Create new node of tree
TreeNode node = new TreeNode(key, this.root);
if (this.root == null)
{
this.root = node;
}
else if (isCombine(node) == true)
{
//  When need to combine two sibling
this.root = merge(node, this.root);
}
else
{
this.root = node;
}
}
//  This is sort add subtree
public TreeNode addSubTree(TreeNode front, TreeNode subtree)
{
if (front == null)
{
return subtree;
}
else if (subtree.counter > front.counter)
{
return front;
}
else
{
//  Add subtree before front tree
subtree.sibling = front;
if (isCombine(subtree) == true)
{
//  Returns the  new result after added subtree
return merge(subtree, front);
}
return subtree;
}
}
//  In-order view of Binomial Heap from left to right in top tree
public void printTree(TreeNode node)
{
if (node == null)
{
return;
}
Console.Write("  " + node.key);
//  Visit of child and sibling nodes
printTree(node.child);
printTree(node.sibling);
}
//  Return minimum key value of tree
public int minimum()
{
if (this.root == null)
{
//  When empty tree
return -1;
}
TreeNode auxiliary = this.root;
int result = this.root.key;
//  Find last node
while (auxiliary != null)
{
if (result > auxiliary.key)
{
result = auxiliary.key;
}
auxiliary = auxiliary.sibling;
}
return result;
}
//  This is handles request to delete minimum nodes of Binomial heap
public void deleteMinKey()
{
if (this.root == null)
{
Console.Write("\n Empty Tree \n");
return;
}
//  Define some useful variables
TreeNode node = null;
TreeNode auxiliary = null;
TreeNode small = this.root;
//  Starting to first this
node = this.root;
//  Find min key subtree in top of Binomial heap
while (node.sibling != null)
{
if (node.sibling.key < small.key)
{
auxiliary = node;
small = node.sibling;
}
//  Visits to next sibling
node = node.sibling;
}
if (auxiliary != null)
{
//  Segregate the minimum key subtree
auxiliary.sibling = small.sibling;
}
else
{
//  Delete first subtree
this.root = small.sibling;
}
//  Get the child of deleted min key node
node = small.child;
//  Add the delete node child into actual tree
while (node != null)
{
auxiliary = node;
node = node.sibling;
// Set default value of subtree
auxiliary.sibling = null;
auxiliary.parent = null;
//  Add subtree to actual tree
}
Console.Write("\n After Delete small Node : " + small.key + " \n");
//  Delete minimum value key node
small = null;
printTree(this.root);
}
public static void Main(String[] args)
{
BinomialHeap tree = new BinomialHeap();
tree.insert(6);
tree.insert(5);
tree.insert(9);
tree.insert(3);
tree.insert(4);
tree.insert(11);
tree.insert(1);
tree.insert(7);
tree.insert(12);
tree.insert(10);
tree.insert(21);
Console.Write("\n Constructing Binomial Heap \n");
/*
Constructing of Binomial Heap
==========================
21-------10 ----------- 1
|            / | \
|           /  |  \
12         3   4   7
/ \  |
/   \ |
5   9 11
|
|
6
==========================
Logical view
*/
tree.printTree(tree.root);
Console.Write("\n Minimum node : " + tree.minimum() + " ");
tree.deleteMinKey();
/*
After Detete Min Node 1
==========================

7 ------------  3
|            /  |  \
|           /   |   \
21         4    5    9
/ \   |
/   \  |
10   11 6
|
|
12
==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 3
==========================

9 ------------  4
/  |  \
/   |   \
5   10   11
/ \   |
/   \  |
7     6 12
|
|
21
==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 4
==========================

5
/ | \
/  |  \
9   7   6
/ |   |
10  11  |
|       21
12

==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 5
=========================

6 -------7 ----------- 9
|           / |
|          /  |
21        10  11
|
|
12
Logical view
*/
Console.Write("\n");
}
}``````

#### Output

`````` Constructing Binomial Heap
21  10  12  1  3  5  6  9  4  11  7
Minimum node : 1
After Delete small Node : 1
7  21  3  4  10  12  11  5  6  9
After Delete small Node : 3
9  4  5  7  21  6  10  12  11
After Delete small Node : 4
5  9  10  12  11  7  21  6
After Delete small Node : 5
6  7  21  9  10  12  11``````
``````<?php
/*
Php program
Binomial Heap Node deletion
*/
//  Define TreeNode
class TreeNode
{
public \$key;
public \$counter;
public \$sibling;
public \$parent;
public \$child;

function __construct(\$key, \$sibling)
{
\$this->key = \$key;
\$this->sibling = \$sibling;
//  Set default value of node
\$this->child = null;
\$this->parent = null;
\$this->counter = 0;
}
}
//  Define BinomialHeap
class BinomialHeap
{
public \$root;

function __construct()
{
\$this->root = null;
}
//  Determine that whether the given node and next sibling tree have same number of children nodes
public	function isCombine(\$node)
{
if (\$node != null
&& \$node->sibling != null
&& \$node->counter == \$node->sibling->counter)
{
return true;
}
else
{
return false;
}
}
//  This is attack child tree into parent tree
public	function changeRelation(\$parentNode, \$childNode)
{
if (\$parentNode->sibling == \$childNode)
{
\$parentNode->sibling = \$childNode->sibling;
}
\$childNode->sibling = \$parentNode->child;
\$parentNode->child = \$childNode;
\$childNode->parent = \$parentNode;
\$parentNode->counter += 1;
return \$parentNode;
}
//  Recursively merging of two tree
public	function merge(\$node1, \$node2)
{
\$temp = null;
if (\$node1->key < \$node2->key)
{
\$temp = \$this->changeRelation(\$node1, \$node2);
}
else
{
\$temp = \$this->changeRelation(\$node2, \$node1);
}
if (\$this->isCombine(\$temp) == true)
{
\$temp = \$this->merge(\$temp, \$temp->sibling);
}
return \$temp;
}
//  Handles the request of add new key into the tree
public	function insert(\$key)
{
//  Create new node of tree
\$node = new TreeNode(\$key, \$this->root);
if (\$this->root == null)
{
\$this->root = \$node;
}
else if (\$this->isCombine(\$node) == true)
{
//  When need to combine two sibling
\$this->root = \$this->merge(\$node, \$this->root);
}
else
{
\$this->root = \$node;
}
}
//  This is sort add subtree
{
if (\$front == null)
{
return \$subtree;
}
else if (\$subtree->counter > \$front->counter)
{
return \$front;
}
else
{
//  Add subtree before front tree
\$subtree->sibling = \$front;
if (\$this->isCombine(\$subtree) == true)
{
//  Returns the  new result after added subtree
return \$this->merge(\$subtree, \$front);
}
return \$subtree;
}
}
//  In-order view of Binomial Heap from left to right in top tree
public	function printTree(\$node)
{
if (\$node == null)
{
return;
}
echo "  ". \$node->key;
//  Visit of child and sibling nodes
\$this->printTree(\$node->child);
\$this->printTree(\$node->sibling);
}
//  Return minimum key value of tree
public	function minimum()
{
if (\$this->root == null)
{
//  When empty tree
return -1;
}
\$auxiliary = \$this->root;
\$result = \$this->root->key;
//  Find last node
while (\$auxiliary != null)
{
if (\$result > \$auxiliary->key)
{
\$result = \$auxiliary->key;
}
\$auxiliary = \$auxiliary->sibling;
}
return \$result;
}
//  This is handles request to delete minimum nodes of Binomial heap
public	function deleteMinKey()
{
if (\$this->root == null)
{
echo "\n Empty Tree \n";
return;
}
//  Define some useful variables
\$node = null;
\$auxiliary = null;
\$small = \$this->root;
//  Starting to first this
\$node = \$this->root;
//  Find min key subtree in top of Binomial heap
while (\$node->sibling != null)
{
if (\$node->sibling->key < \$small->key)
{
\$auxiliary = \$node;
\$small = \$node->sibling;
}
//  Visits to next sibling
\$node = \$node->sibling;
}
if (\$auxiliary != null)
{
//  Segregate the minimum key subtree
\$auxiliary->sibling = \$small->sibling;
}
else
{
//  Delete first subtree
\$this->root = \$small->sibling;
}
//  Get the child of deleted min key node
\$node = \$small->child;
//  Add the delete node child into actual tree
while (\$node != null)
{
\$auxiliary = \$node;
\$node = \$node->sibling;
// Set default value of subtree
\$auxiliary->sibling = null;
\$auxiliary->parent = null;
//  Add subtree to actual tree
}
echo "\n After Delete small Node : ". \$small->key ." \n";
//  Delete minimum value key node
\$small = null;
\$this->printTree(\$this->root);
}
}

function main()
{
\$tree = new BinomialHeap();
\$tree->insert(6);
\$tree->insert(5);
\$tree->insert(9);
\$tree->insert(3);
\$tree->insert(4);
\$tree->insert(11);
\$tree->insert(1);
\$tree->insert(7);
\$tree->insert(12);
\$tree->insert(10);
\$tree->insert(21);
echo "\n Constructing Binomial Heap \n";
/*
Constructing of Binomial Heap
==========================
21-------10 ----------- 1
|            / | \
|           /  |  \
12         3   4   7
/ \  |
/   \ |
5   9 11
|
|
6
==========================
Logical view
*/
\$tree->printTree(\$tree->root);
echo "\n Minimum node : ". \$tree->minimum() ." ";
\$tree->deleteMinKey();
/*
After Detete Min Node 1
==========================

7 ------------  3
|            /  |  \
|           /   |   \
21         4    5    9
/ \   |
/   \  |
10   11 6
|
|
12
==========================
Logical view
*/
\$tree->deleteMinKey();
/*
After Detete Min Node 3
==========================

9 ------------  4
/  |  \
/   |   \
5   10   11
/ \   |
/   \  |
7     6 12
|
|
21
==========================
Logical view
*/
\$tree->deleteMinKey();
/*
After Detete Min Node 4
==========================

5
/ | \
/  |  \
9   7   6
/ |   |
10  11  |
|       21
12

==========================
Logical view
*/
\$tree->deleteMinKey();
/*
After Detete Min Node 5
=========================

6 -------7 ----------- 9
|           / |
|          /  |
21        10  11
|
|
12
Logical view
*/
echo "\n";
}
main();``````

#### Output

`````` Constructing Binomial Heap
21  10  12  1  3  5  6  9  4  11  7
Minimum node : 1
After Delete small Node : 1
7  21  3  4  10  12  11  5  6  9
After Delete small Node : 3
9  4  5  7  21  6  10  12  11
After Delete small Node : 4
5  9  10  12  11  7  21  6
After Delete small Node : 5
6  7  21  9  10  12  11``````
``````/*
Node Js program
Binomial Heap Node deletion
*/
//  Define TreeNode
class TreeNode
{
constructor(key, sibling)
{
this.key = key;
this.sibling = sibling;
//  Set default value of node
this.child = null;
this.parent = null;
this.counter = 0;
}
}
//  Define BinomialHeap
class BinomialHeap
{
constructor()
{
this.root = null;
}
//  Determine that whether the given node and
// next sibling tree have same number of children nodes
isCombine(node)
{
if (node != null && node.sibling != null
&& node.counter == node.sibling.counter)
{
return true;
}
else
{
return false;
}
}
//  This is attack child tree into parent tree
changeRelation(parentNode, childNode)
{
if (parentNode.sibling == childNode)
{
parentNode.sibling = childNode.sibling;
}
childNode.sibling = parentNode.child;
parentNode.child = childNode;
childNode.parent = parentNode;
parentNode.counter += 1;
return parentNode;
}
//  Recursively merging of two tree
merge(node1, node2)
{
var temp = null;
if (node1.key < node2.key)
{
temp = this.changeRelation(node1, node2);
}
else
{
temp = this.changeRelation(node2, node1);
}
if (this.isCombine(temp) == true)
{
temp = this.merge(temp, temp.sibling);
}
return temp;
}
//  Handles the request of add new key into the tree
insert(key)
{
//  Create new node of tree
var node = new TreeNode(key, this.root);
if (this.root == null)
{
this.root = node;
}
else if (this.isCombine(node) == true)
{
//  When need to combine two sibling
this.root = this.merge(node, this.root);
}
else
{
this.root = node;
}
}
//  This is sort add subtree
{
if (front == null)
{
return subtree;
}
else if (subtree.counter > front.counter)
{
return front;
}
else
{
//  Add subtree before front tree
subtree.sibling = front;
if (this.isCombine(subtree) == true)
{
//  Returns the  new result after added subtree
return this.merge(subtree, front);
}
return subtree;
}
}
//  In-order view of Binomial Heap from left to right in top tree
printTree(node)
{
if (node == null)
{
return;
}
process.stdout.write("  " + node.key);
//  Visit of child and sibling nodes
this.printTree(node.child);
this.printTree(node.sibling);
}
//  Return minimum key value of tree
minimum()
{
if (this.root == null)
{
//  When empty tree
return -1;
}
var auxiliary = this.root;
var result = this.root.key;
//  Find last node
while (auxiliary != null)
{
if (result > auxiliary.key)
{
result = auxiliary.key;
}
auxiliary = auxiliary.sibling;
}
return result;
}
//  This is handles request to delete minimum nodes of Binomial heap
deleteMinKey()
{
if (this.root == null)
{
process.stdout.write("\n Empty Tree \n");
return;
}
//  Define some useful variables
var node = null;
var auxiliary = null;
var small = this.root;
//  Starting to first this
node = this.root;
//  Find min key subtree in top of Binomial heap
while (node.sibling != null)
{
if (node.sibling.key < small.key)
{
auxiliary = node;
small = node.sibling;
}
//  Visits to next sibling
node = node.sibling;
}
if (auxiliary != null)
{
//  Segregate the minimum key subtree
auxiliary.sibling = small.sibling;
}
else
{
//  Delete first subtree
this.root = small.sibling;
}
//  Get the child of deleted min key node
node = small.child;
//  Add the delete node child into actual tree
while (node != null)
{
auxiliary = node;
node = node.sibling;
// Set default value of subtree
auxiliary.sibling = null;
auxiliary.parent = null;
//  Add subtree to actual tree
}
process.stdout.write("\n After Delete small Node : " + small.key + " \n");
//  Delete minimum value key node
small = null;
this.printTree(this.root);
}
}

function main()
{
var tree = new BinomialHeap();
tree.insert(6);
tree.insert(5);
tree.insert(9);
tree.insert(3);
tree.insert(4);
tree.insert(11);
tree.insert(1);
tree.insert(7);
tree.insert(12);
tree.insert(10);
tree.insert(21);
process.stdout.write("\n Constructing Binomial Heap \n");
/*
Constructing of Binomial Heap
==========================
21-------10 ----------- 1
|            / | \
|           /  |  \
12         3   4   7
/ \  |
/   \ |
5   9 11
|
|
6
==========================
Logical view
*/
tree.printTree(tree.root);
process.stdout.write("\n Minimum node : " + tree.minimum() + " ");
tree.deleteMinKey();
/*
After Detete Min Node 1
==========================

7 ------------  3
|            /  |  \
|           /   |   \
21         4    5    9
/ \   |
/   \  |
10   11 6
|
|
12
==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 3
==========================

9 ------------  4
/  |  \
/   |   \
5   10   11
/ \   |
/   \  |
7     6 12
|
|
21
==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 4
==========================

5
/ | \
/  |  \
9   7   6
/ |   |
10  11  |
|       21
12

==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 5
=========================

6 -------7 ----------- 9
|           / |
|          /  |
21        10  11
|
|
12
Logical view
*/
process.stdout.write("\n");
}
main();``````

#### Output

`````` Constructing Binomial Heap
21  10  12  1  3  5  6  9  4  11  7
Minimum node : 1
After Delete small Node : 1
7  21  3  4  10  12  11  5  6  9
After Delete small Node : 3
9  4  5  7  21  6  10  12  11
After Delete small Node : 4
5  9  10  12  11  7  21  6
After Delete small Node : 5
6  7  21  9  10  12  11``````
``````#  Python 3 program
#  Binomial Heap Node deletion

#  Define TreeNode
class TreeNode :

def __init__(self, key, sibling) :
self.key = key
self.sibling = sibling
#  Set default value of node
self.child = None
self.parent = None
self.counter = 0

#  Define BinomialHeap
class BinomialHeap :

def __init__(self) :
self.root = None

#  Determine that whether the given node and next sibling tree have same number of children nodes
def isCombine(self, node) :
if (node != None
and node.sibling != None
and node.counter == node.sibling.counter) :
return True
else :
return False

#  This is attack child tree into parent tree
def changeRelation(self, parentNode, childNode) :
if (parentNode.sibling == childNode) :
parentNode.sibling = childNode.sibling

childNode.sibling = parentNode.child
parentNode.child = childNode
childNode.parent = parentNode
parentNode.counter += 1
return parentNode

#  Recursively merging of two tree
def merge(self, node1, node2) :
temp = None
if (node1.key < node2.key) :
temp = self.changeRelation(node1, node2)
else :
temp = self.changeRelation(node2, node1)

if (self.isCombine(temp) == True) :
temp = self.merge(temp, temp.sibling)

return temp

#  Handles the request of add new key into the tree
def insert(self, key) :
#  Create new node of tree
node = TreeNode(key, self.root)
if (self.root == None) :
self.root = node

elif(self.isCombine(node) == True) :
#  When need to combine two sibling
self.root = self.merge(node, self.root)
else :
self.root = node

#  This is sort add subtree
if (front == None) :
return subtree

elif(subtree.counter > front.counter) :
return front
else :
#  Add subtree before front tree
subtree.sibling = front
if (self.isCombine(subtree) == True) :
#  Returns the  new result after added subtree
return self.merge(subtree, front)

return subtree

#  In-order view of Binomial Heap from left to right in top tree
def printTree(self, node) :
if (node == None) :
return

print("  ", node.key, end = "")
#  Visit of child and sibling nodes
self.printTree(node.child)
self.printTree(node.sibling)

#  Return minimum key value of tree
def minimum(self) :
if (self.root == None) :
#  When empty tree
return -1

auxiliary = self.root
result = self.root.key
#  Find last node
while (auxiliary != None) :
if (result > auxiliary.key) :
result = auxiliary.key

auxiliary = auxiliary.sibling

return result

#  This is handles request to delete minimum nodes of Binomial heap
def deleteMinKey(self) :
if (self.root == None) :
print("\n Empty Tree \n", end = "")
return

#  Define some useful variables
node = None
auxiliary = None
small = self.root
#  Starting to first this
node = self.root
#  Find min key subtree in top of Binomial heap
while (node.sibling != None) :
if (node.sibling.key < small.key) :
auxiliary = node
small = node.sibling

#  Visits to next sibling
node = node.sibling

if (auxiliary != None) :
#  Segregate the minimum key subtree
auxiliary.sibling = small.sibling
else :
#  Delete first subtree
self.root = small.sibling

#  Get the child of deleted min key node
node = small.child
#  Add the delete node child into actual tree
while (node != None) :
auxiliary = node
node = node.sibling
# Set default value of subtree
auxiliary.sibling = None
auxiliary.parent = None
#  Add subtree to actual tree

print("\n After Delete small Node : ", small.key ," \n", end = "")
#  Delete minimum value key node
small = None
self.printTree(self.root)

def main() :
tree = BinomialHeap()
tree.insert(6)
tree.insert(5)
tree.insert(9)
tree.insert(3)
tree.insert(4)
tree.insert(11)
tree.insert(1)
tree.insert(7)
tree.insert(12)
tree.insert(10)
tree.insert(21)
print("\n Constructing Binomial Heap \n", end = "")
#
#     Constructing of Binomial Heap
#     ==========================
#     21-------10 ----------- 1
#              |            / | \
#              |           /  |  \
#              12         3   4   7
#                        / \  |
#                       /   \ |
#                       5   9 11
#                       |
#                       |
#                       6
#     ==========================
#     Logical view
#

tree.printTree(tree.root)
print("\n Minimum node : ", tree.minimum() ," ", end = "")
tree.deleteMinKey()
#
#     After Detete Min Node 1
#     ==========================
#      7 ------------  3
#      |            /  |  \
#      |           /   |   \
#      21         4    5    9
#                / \   |
#               /   \  |
#              10   11 6
#              |
#              |
#              12
#     ==========================
#     Logical view
#

tree.deleteMinKey()
#
#     After Detete Min Node 3
#     ==========================
#      9 ------------  4
#                   /  |  \
#                  /   |   \
#                 5   10   11
#                / \   |
#               /   \  |
#              7     6 12
#              |
#              |
#              21
#     ==========================
#     Logical view
#

tree.deleteMinKey()
#
#     After Detete Min Node 4
#     ==========================
#                5
#              / | \
#             /  |  \
#            9   7   6
#          / |   |
#        10  11  |
#        |       21
#        12
#     ==========================
#     Logical view
#

tree.deleteMinKey()
#
#     After Detete Min Node 5
#     =========================
#     6 -------7 ----------- 9
#              |           / |
#              |          /  |
#              21        10  11
#                        |
#                        |
#                        12
#     Logical view
#

print("\n", end = "")

if __name__ == "__main__": main()``````

#### Output

`````` Constructing Binomial Heap
21   10   12   1   3   5   6   9   4   11   7
Minimum node :  1
After Delete small Node :  1
7   21   3   4   10   12   11   5   6   9
After Delete small Node :  3
9   4   5   7   21   6   10   12   11
After Delete small Node :  4
5   9   10   12   11   7   21   6
After Delete small Node :  5
6   7   21   9   10   12   11``````
``````#  Ruby program
#  Binomial Heap Node deletion

#  Define TreeNode
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :key, :counter, :sibling, :parent, :child
attr_accessor :key, :counter, :sibling, :parent, :child

def initialize(key, sibling)
self.key = key
self.sibling = sibling
#  Set default value of node
self.child = nil
self.parent = nil
self.counter = 0
end

end

#  Define BinomialHeap
class BinomialHeap
# Define the accessor and reader of class BinomialHeap
attr_accessor :root

def initialize()
self.root = nil
end

#  Determine that whether the given node and next sibling tree have same number of children nodes
def isCombine(node)
if (node != nil && node.sibling != nil && node.counter == node.sibling.counter)
return true
else
return false
end

end

#  This is attack child tree into parent tree
def changeRelation(parentNode, childNode)
if (parentNode.sibling == childNode)
parentNode.sibling = childNode.sibling
end

childNode.sibling = parentNode.child
parentNode.child = childNode
childNode.parent = parentNode
parentNode.counter += 1
return parentNode
end

#  Recursively merging of two tree
def merge(node1, node2)
temp = nil
if (node1.key < node2.key)
temp = self.changeRelation(node1, node2)
else
temp = self.changeRelation(node2, node1)
end

if (self.isCombine(temp) == true)
temp = self.merge(temp, temp.sibling)
end

return temp
end

#  Handles the request of add new key into the tree
def insert(key)
#  Create new node of tree
node = TreeNode.new(key, self.root)
if (self.root == nil)
self.root = node
elsif(self.isCombine(node) == true)
#  When need to combine two sibling
self.root = self.merge(node, self.root)
else
self.root = node
end

end

#  This is sort add subtree
if (front == nil)
return subtree
elsif(subtree.counter > front.counter)
return front
else
#  Add subtree before front tree
subtree.sibling = front
if (self.isCombine(subtree) == true)
#  Returns the  new result after added subtree
return self.merge(subtree, front)
end

return subtree
end

end

#  In-order view of Binomial Heap from left to right in top tree
def printTree(node)
if (node == nil)
return
end

print("  ", node.key)
#  Visit of child and sibling nodes
self.printTree(node.child)
self.printTree(node.sibling)
end

#  Return minimum key value of tree
def minimum()
if (self.root == nil)
#  When empty tree
return -1
end

auxiliary = self.root
result = self.root.key
#  Find last node
while (auxiliary != nil)
if (result > auxiliary.key)
result = auxiliary.key
end

auxiliary = auxiliary.sibling
end

return result
end

#  This is handles request to delete minimum nodes of Binomial heap
def deleteMinKey()
if (self.root == nil)
print("\n Empty Tree \n")
return
end

#  Define some useful variables
node = nil
auxiliary = nil
small = self.root
#  Starting to first this
node = self.root
#  Find min key subtree in top of Binomial heap
while (node.sibling != nil)
if (node.sibling.key < small.key)
auxiliary = node
small = node.sibling
end

#  Visits to next sibling
node = node.sibling
end

if (auxiliary != nil)
#  Segregate the minimum key subtree
auxiliary.sibling = small.sibling
else
#  Delete first subtree
self.root = small.sibling
end

#  Get the child of deleted min key node
node = small.child
#  Add the delete node child into actual tree
while (node != nil)
auxiliary = node
node = node.sibling
# Set default value of subtree
auxiliary.sibling = nil
auxiliary.parent = nil
#  Add subtree to actual tree
end

print("\n After Delete small Node : ", small.key ," \n")
#  Delete minimum value key node
small = nil
self.printTree(self.root)
end

end

def main()
tree = BinomialHeap.new()
tree.insert(6)
tree.insert(5)
tree.insert(9)
tree.insert(3)
tree.insert(4)
tree.insert(11)
tree.insert(1)
tree.insert(7)
tree.insert(12)
tree.insert(10)
tree.insert(21)
print("\n Constructing Binomial Heap \n")
#
#     Constructing of Binomial Heap
#     ==========================
#     21-------10 ----------- 1
#              |            / | \
#              |           /  |  \
#              12         3   4   7
#                        / \  |
#                       /   \ |
#                       5   9 11
#                       |
#                       |
#                       6
#     ==========================
#     Logical view
#

tree.printTree(tree.root)
print("\n Minimum node : ", tree.minimum() ," ")
tree.deleteMinKey()
#
#     After Detete Min Node 1
#     ==========================
#      7 ------------  3
#      |            /  |  \
#      |           /   |   \
#      21         4    5    9
#                / \   |
#               /   \  |
#              10   11 6
#              |
#              |
#              12
#     ==========================
#     Logical view
#

tree.deleteMinKey()
#
#     After Detete Min Node 3
#     ==========================
#      9 ------------  4
#                   /  |  \
#                  /   |   \
#                 5   10   11
#                / \   |
#               /   \  |
#              7     6 12
#              |
#              |
#              21
#     ==========================
#     Logical view
#

tree.deleteMinKey()
#
#     After Detete Min Node 4
#     ==========================
#                5
#              / | \
#             /  |  \
#            9   7   6
#          / |   |
#        10  11  |
#        |       21
#        12
#     ==========================
#     Logical view
#

tree.deleteMinKey()
#
#     After Detete Min Node 5
#     =========================
#     6 -------7 ----------- 9
#              |           / |
#              |          /  |
#              21        10  11
#                        |
#                        |
#                        12
#     Logical view
#

print("\n")
end

main()``````

#### Output

`````` Constructing Binomial Heap
21  10  12  1  3  5  6  9  4  11  7
Minimum node : 1
After Delete small Node : 1
7  21  3  4  10  12  11  5  6  9
After Delete small Node : 3
9  4  5  7  21  6  10  12  11
After Delete small Node : 4
5  9  10  12  11  7  21  6
After Delete small Node : 5
6  7  21  9  10  12  11
``````
``````/*
Scala program
Binomial Heap Node deletion
*/
//  Define TreeNode
class TreeNode(var key: Int ,
var counter: Int ,
var sibling: TreeNode ,
var parent: TreeNode ,
var child: TreeNode)
{
def this(key: Int, sibling: TreeNode)
{
this(key, 0, sibling, null, null);
}
}
//  Define BinomialHeap
class BinomialHeap(var root: TreeNode)
{
def this()
{
this(null);
}
//  Determine that whether the given node and next sibling tree have same number of children nodes
def isCombine(node: TreeNode): Boolean = {
if (node != null
&& node.sibling != null
&& node.counter == node.sibling.counter)
{
return true;
}
else
{
return false;
}
}
//  This is attack child tree into parent tree
def changeRelation(parentNode: TreeNode, childNode: TreeNode): TreeNode = {
if (parentNode.sibling == childNode)
{
parentNode.sibling = childNode.sibling;
}
childNode.sibling = parentNode.child;
parentNode.child = childNode;
childNode.parent = parentNode;
parentNode.counter += 1;
return parentNode;
}
//  Recursively merging of two tree
def merge(node1: TreeNode, node2: TreeNode): TreeNode = {
var temp: TreeNode = null;
if (node1.key < node2.key)
{
temp = this.changeRelation(node1, node2);
}
else
{
temp = this.changeRelation(node2, node1);
}
if (this.isCombine(temp) == true)
{
temp = this.merge(temp, temp.sibling);
}
return temp;
}
//  Handles the request of add new key into the tree
def insert(key: Int): Unit = {
//  Create new node of tree
var node: TreeNode = new TreeNode(key, this.root);
if (this.root == null)
{
this.root = node;
}
else if (this.isCombine(node) == true)
{
//  When need to combine two sibling
this.root = this.merge(node, this.root);
}
else
{
this.root = node;
}
}
//  This is sort add subtree
def addSubTree(front: TreeNode, subtree: TreeNode): TreeNode = {
if (front == null)
{
return subtree;
}
else if (subtree.counter > front.counter)
{
return front;
}
else
{
//  Add subtree before front tree
subtree.sibling = front;
if (this.isCombine(subtree) == true)
{
//  Returns the  new result after added subtree
return this.merge(subtree, front);
}
return subtree;
}
}
//  In-order view of Binomial Heap from left to right in top tree
def printTree(node: TreeNode): Unit = {
if (node == null)
{
return;
}
print("  " + node.key);
//  Visit of child and sibling nodes
this.printTree(node.child);
this.printTree(node.sibling);
}
//  Return minimum key value of tree
def minimum(): Int = {
if (this.root == null)
{
//  When empty tree
return -1;
}
var auxiliary: TreeNode = this.root;
var result: Int = this.root.key;
//  Find last node
while (auxiliary != null)
{
if (result > auxiliary.key)
{
result = auxiliary.key;
}
auxiliary = auxiliary.sibling;
}
return result;
}
//  This is handles request to delete minimum nodes of Binomial heap
def deleteMinKey(): Unit = {
if (this.root == null)
{
print("\n Empty Tree \n");
return;
}
//  Define some useful variables
var node: TreeNode = null;
var auxiliary: TreeNode = null;
var small: TreeNode = this.root;
//  Starting to first this
node = this.root;
//  Find min key subtree in top of Binomial heap
while (node.sibling != null)
{
if (node.sibling.key < small.key)
{
auxiliary = node;
small = node.sibling;
}
//  Visits to next sibling
node = node.sibling;
}
if (auxiliary != null)
{
//  Segregate the minimum key subtree
auxiliary.sibling = small.sibling;
}
else
{
//  Delete first subtree
this.root = small.sibling;
}
//  Get the child of deleted min key node
node = small.child;
//  Add the delete node child into actual tree
while (node != null)
{
auxiliary = node;
node = node.sibling;
// Set default value of subtree
auxiliary.sibling = null;
auxiliary.parent = null;
//  Add subtree to actual tree
}
print("\n After Delete small Node : " + small.key + " \n");
//  Delete minimum value key node
small = null;
this.printTree(this.root);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinomialHeap = new BinomialHeap();
tree.insert(6);
tree.insert(5);
tree.insert(9);
tree.insert(3);
tree.insert(4);
tree.insert(11);
tree.insert(1);
tree.insert(7);
tree.insert(12);
tree.insert(10);
tree.insert(21);
print("\n Constructing Binomial Heap \n");
/*
Constructing of Binomial Heap
==========================
21-------10 ----------- 1
|            / | \
|           /  |  \
12         3   4   7
/ \  |
/   \ |
5   9 11
|
|
6
==========================
Logical view
*/
tree.printTree(tree.root);
print("\n Minimum node : " + tree.minimum() + " ");
tree.deleteMinKey();
/*
After Detete Min Node 1
==========================

7 ------------  3
|            /  |  \
|           /   |   \
21         4    5    9
/ \   |
/   \  |
10   11 6
|
|
12
==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 3
==========================

9 ------------  4
/  |  \
/   |   \
5   10   11
/ \   |
/   \  |
7     6 12
|
|
21
==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 4
==========================

5
/ | \
/  |  \
9   7   6
/ |   |
10  11  |
|       21
12

==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 5
=========================

6 -------7 ----------- 9
|           / |
|          /  |
21        10  11
|
|
12
Logical view
*/
print("\n");
}
}``````

#### Output

`````` Constructing Binomial Heap
21  10  12  1  3  5  6  9  4  11  7
Minimum node : 1
After Delete small Node : 1
7  21  3  4  10  12  11  5  6  9
After Delete small Node : 3
9  4  5  7  21  6  10  12  11
After Delete small Node : 4
5  9  10  12  11  7  21  6
After Delete small Node : 5
6  7  21  9  10  12  11``````
``````/*
Swift 4 program
Binomial Heap Node deletion
*/
//  Define TreeNode
class TreeNode
{
var key: Int;
var counter: Int;
var sibling: TreeNode? ;
var parent: TreeNode? ;
var child: TreeNode? ;
init(_ key: Int, _ sibling: TreeNode? )
{
self.key = key;
self.sibling = sibling;
//  Set default value of node
self.child = nil;
self.parent = nil;
self.counter = 0;
}
}
//  Define BinomialHeap
class BinomialHeap
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
//  Determine that whether the given node and next sibling tree have same number of children nodes
func isCombine(_ node: TreeNode? )->Bool
{
if (node != nil && node!.sibling != nil && node!.counter == node!.sibling!.counter)
{
return true;
}
else
{
return false;
}
}
//  This is attack child tree into parent tree
func changeRelation(_ parentNode: TreeNode? , _ childNode : TreeNode? )->TreeNode?
{
if (parentNode!.sibling === childNode)
{
parentNode!.sibling = childNode!.sibling;
}
childNode!.sibling = parentNode!.child;parentNode!.child = childNode;childNode!.parent = parentNode;parentNode!.counter += 1;
return parentNode;
}
//  Recursively merging of two tree
func merge(_ node1: TreeNode? , _ node2 : TreeNode? )->TreeNode?
{
var temp: TreeNode? = nil;
if (node1!.key < node2!.key)
{
temp = self.changeRelation(node1, node2);
}
else
{
temp = self.changeRelation(node2, node1);
}
if (self.isCombine(temp) == true)
{
temp = self.merge(temp, temp!.sibling);
}
return temp;
}
//  Handles the request of add new key into the tree
func insert(_ key: Int)
{
//  Create new node of tree
let node: TreeNode? = TreeNode(key, self.root);
if (self.root == nil)
{
self.root = node;
}
else if (self.isCombine(node) == true)
{
//  When need to combine two sibling
self.root = self.merge(node, self.root);
}
else
{
self.root = node;
}
}
//  This is sort add subtree
func addSubTree(_ front: TreeNode? , _ subtree : TreeNode? )->TreeNode?
{
if (front == nil)
{
return subtree;
}
else if (subtree!.counter > front!.counter)
{
return front;
}
else
{
//  Add subtree before front tree
subtree!.sibling = front;
if (self.isCombine(subtree) == true)
{
//  Returns the  new result after added subtree
return self.merge(subtree, front);
}
return subtree;
}
}
//  In-order view of Binomial Heap from left to right in top tree
func printTree(_ node: TreeNode? )
{
if (node == nil)
{
return;
}
print("  ", node!.key, terminator: "");
//  Visit of child and sibling nodes
self.printTree(node!.child);
self.printTree(node!.sibling);
}
//  Return minimum key value of tree
func minimum()->Int
{
if (self.root == nil)
{
//  When empty tree
return -1;
}
var auxiliary: TreeNode? = self.root;
var result: Int = self.root!.key;
//  Find last node
while (auxiliary != nil)
{
if (result > auxiliary!.key)
{
result = auxiliary!.key;
}
auxiliary = auxiliary!.sibling;
}
return result;
}
//  This is handles request to delete minimum nodes of Binomial heap
func deleteMinKey()
{
if (self.root == nil)
{
print("\n Empty Tree \n", terminator: "");
return;
}
//  Define some useful variables
var node: TreeNode? = nil;
var auxiliary: TreeNode? = nil;
var small: TreeNode? = self.root;
//  Starting to first this
node = self.root;
//  Find min key subtree in top of Binomial heap
while (node!.sibling != nil)
{
if (node!.sibling!.key < small!.key)
{
auxiliary = node;
small = node!.sibling;
}
//  Visits to next sibling
node = node!.sibling;
}
if (auxiliary != nil)
{
//  Segregate the minimum key subtree
auxiliary!.sibling = small!.sibling;
}
else
{
//  Delete first subtree
self.root = small!.sibling;
}
//  Get the child of deleted min key node
node = small!.child;
//  Add the delete node child into actual tree
while (node != nil)
{
auxiliary = node;
node = node!.sibling;
// Set default value of subtree
auxiliary!.sibling = nil;
auxiliary!.parent = nil;
//  Add subtree to actual tree
}
print("\n After Delete small Node : ", small!.key ," \n", terminator: "");
//  Delete minimum value key node
small = nil;
self.printTree(self.root);
}
}
func main()
{
let tree: BinomialHeap = BinomialHeap();
tree.insert(6);
tree.insert(5);
tree.insert(9);
tree.insert(3);
tree.insert(4);
tree.insert(11);
tree.insert(1);
tree.insert(7);
tree.insert(12);
tree.insert(10);
tree.insert(21);
print("\n Constructing Binomial Heap \n", terminator: "");
/*
Constructing of Binomial Heap
==========================
21-------10 ----------- 1
|            / | \
|           /  |  \
12         3   4   7
/ \  |
/   \ |
5   9 11
|
|
6
==========================
Logical view
*/
tree.printTree(tree.root);
print("\n Minimum node : ", tree.minimum() ," ", terminator: "");
tree.deleteMinKey();
/*
After Detete Min Node 1
==========================

7 ------------  3
|            /  |  \
|           /   |   \
21         4    5    9
/ \   |
/   \  |
10   11 6
|
|
12
==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 3
==========================

9 ------------  4
/  |  \
/   |   \
5   10   11
/ \   |
/   \  |
7     6 12
|
|
21
==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 4
==========================

5
/ | \
/  |  \
9   7   6
/ |   |
10  11  |
|       21
12

==========================
Logical view
*/
tree.deleteMinKey();
/*
After Detete Min Node 5
=========================

6 -------7 ----------- 9
|           / |
|          /  |
21        10  11
|
|
12
Logical view
*/
print("\n", terminator: "");
}
main();``````

#### Output

`````` Constructing Binomial Heap
21   10   12   1   3   5   6   9   4   11   7
Minimum node :  1
After Delete small Node :  1
7   21   3   4   10   12   11   5   6   9
After Delete small Node :  3
9   4   5   7   21   6   10   12   11
After Delete small Node :  4
5   9   10   12   11   7   21   6
After Delete small Node :  5
6   7   21   9   10   12   11``````

## Time Complexity

The time complexity of the delete operation in a binomial heap is dominated by the merging process, which takes O(log n) time. This is because the merging of binomial trees involves performing a series of pairwise merges, and the number of trees is reduced by half with each merge.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post