Skip to main content

Binomial Heap Node deletion

Here given code implementation process.

// 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)
    {
        // When add subtree node
        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)
    {
        front->sibling = addSubTree(front->sibling, subtree);
    }
    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
        {
            // Add subtree are valid
            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
        tree->root = addSubTree(tree->root, auxiliary);
    }
    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();
    // Add tree element
    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)
    {
        // When add subtree node
        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)
    {
        front.sibling = addSubTree(front.sibling, subtree);
      	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);
        }
       
        // Add subtree are valid
        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
            this.root = addSubTree(this.root, auxiliary);
        }
        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();
    // Add tree element
    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)
		{
			//  When add subtree node
			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
	TreeNode *addSubTree(TreeNode *front, TreeNode *subtree)
	{
		if (front == NULL)
		{
			return subtree;
		}
		else if (subtree->counter > front->counter)
		{
			front->sibling = this->addSubTree(front->sibling, subtree);
			return front;
		}
		else
		{
			//  Add subtree are valid
			//  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
			this->root = this->addSubTree(this->root, auxiliary);
		}
		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();
	//  Add tree element
	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)
		{
			//  When add subtree node
			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)
		{
			front.sibling = addSubTree(front.sibling, subtree);
			return front;
		}
		else
		{
			//  Add subtree are valid
			//  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
			this.root = addSubTree(this.root, auxiliary);
		}
		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();
		//  Add tree element
		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)
		{
			//  When add subtree node
			$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
	public	function addSubTree($front, $subtree)
	{
		if ($front == null)
		{
			return $subtree;
		}
		else if ($subtree->counter > $front->counter)
		{
			$front->sibling = $this->addSubTree($front->sibling, $subtree);
			return $front;
		}
		else
		{
			//  Add subtree are valid
			//  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
			$this->root = $this->addSubTree($this->root, $auxiliary);
		}
		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();
	//  Add tree element
	$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)
		{
			//  When add subtree node
			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
	addSubTree(front, subtree)
	{
		if (front == null)
		{
			return subtree;
		}
		else if (subtree.counter > front.counter)
		{
			front.sibling = this.addSubTree(front.sibling, subtree);
			return front;
		}
		else
		{
			//  Add subtree are valid
			//  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
			this.root = this.addSubTree(this.root, auxiliary);
		}
		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();
	//  Add tree element
	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) :
			#  When add subtree node
			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
	def addSubTree(self, front, subtree) :
		if (front == None) :
			return subtree
		
		elif(subtree.counter > front.counter) :
			front.sibling = self.addSubTree(front.sibling, subtree)
			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)
			
			#  Add subtree are valid
			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
			self.root = self.addSubTree(self.root, auxiliary)
		
		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()
	#  Add tree element
	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_reader :root
	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) 
			#  When add subtree node
			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
	def addSubTree(front, subtree) 
		if (front == nil) 
			return subtree
		elsif(subtree.counter > front.counter) 
			front.sibling = self.addSubTree(front.sibling, subtree)
			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

			#  Add subtree are valid
			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
			self.root = self.addSubTree(self.root, auxiliary)
		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()
	#  Add tree element
	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)
		{
			//  When add subtree node
			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)
		{
			front.sibling = this.addSubTree(front.sibling, subtree);
			return front;
		}
		else
		{
			//  Add subtree are valid
			//  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
			this.root = this.addSubTree(this.root, auxiliary);
		}
		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();
		//  Add tree element
		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)
		{
			//  When add subtree node
			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)
		{
			front!.sibling = self.addSubTree(front!.sibling, subtree);
			return front;
		}
		else
		{
			//  Add subtree are valid
			//  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
			self.root = self.addSubTree(self.root, auxiliary);
		}
		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();
	//  Add tree element
	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




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.

New Comment