Posted on by Kalkicode
Code Heap

Construct Binomial Heap

A Binomial Heap is a data structure that consists of a collection of Binomial Trees. Each Binomial Tree in the heap follows a specific structure, in which each node has at most two children, and the value of each child is greater than or equal to the value of its parent.

Binomial Heaps are particularly useful in priority queue applications because they support efficient insertions, deletions, and extractions of the minimum element. In a Binomial Heap, the minimum element is always stored at the root of one of the Binomial Trees, which makes finding and removing the minimum element very efficient.

Binomial Heaps also have a very efficient union operation, which allows two Binomial Heaps to be combined into a single Binomial Heap in O(log n) time, where n is the total number of elements in the two heaps.

Overall, Binomial Heaps are a very powerful and versatile data structure that can be used in a wide range of applications.

Here given code implementation process.

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

/*
    C program 
    Construct Binomial Heap
*/
// Define TreeNode
struct TreeNode
{
    int key;
    int child_count;
    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->child_count = 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->child_count == node->sibling->child_count)
    {
        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->child_count += 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;
    }
}

// In-order view of Binomial Heap from left to right in top tree
void print_tree(struct TreeNode *node)
{
    if (node == NULL)
    {
        return;
    }
    printf("  %d", node->key);
    // Visit of child and sibling nodes
    print_tree(node->child);
    print_tree(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;
}

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);
    insert(tree, 14);
    insert(tree, 6);
    printf("\n Constructing Binomial Heap \n");
    /*
    Constructing of Binomial Heap
    ==========================
    6-------10 ------------- 1
           / |            /  | \   
         14  |           /   |  \
         |   12         3    4   7
         21            / \   |
                      /   \  |
                      5    9 11
                      |
                      |
                      6
    ==========================
    Logical view    
    */
    print_tree(tree->root);
    printf("\n Minimum node : %d ", minimum(tree->root));
    return 0;
}

Output

 Constructing Binomial Heap
  6  10  14  21  12  1  3  5  6  9  4  11  7
 Minimum node : 1
/*
    Java program 
    Construct Binomial Heap
*/
// 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;
		}
	}
	// 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;
	}
	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);
		tree.insert(14);
		tree.insert(6);
		System.out.print("\n Constructing Binomial Heap \n");
		/*
		Constructing of Binomial Heap
		==========================
		6-------10 -----------  1
		       / |            / | \   
		     14  |           /  |  \
		     |   12         3   4   7
		     21            / \  |
		                  /   \ |
		                  5   9 11
		                  |
		                  |
		                  6
		==========================
		Logical view    
		*/
		tree.printTree(tree.root);
		System.out.print("\n Minimum node : " + tree.minimum() + " ");
	}
}

Output

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

/*
    C++ program 
    Construct Binomial Heap
*/

//  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;
        }
    }
    //  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;
    }
};
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);
    tree.insert(14);
    tree.insert(6);
    cout << "\n Constructing Binomial Heap \n";
    /*
    Constructing of Binomial Heap
    ==========================
    6-------10 -----------  1
           / |            / | \   
         14  |           /  |  \
         |   12         3   4   7
         21            / \  |
                      /   \ |
                      5   9 11
                      |
                      |
                      6
    ==========================
    Logical view    
    */
    tree.printTree(tree.root);
    cout << "\n Minimum node : " << tree.minimum() << " ";
    return 0;
}

Output

 Constructing Binomial Heap
  6  10  14  21  12  1  3  5  6  9  4  11  7
 Minimum node : 1
// Include namespace system
using System;
/*
    C# program 
    Construct Binomial Heap
*/
//  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;
        }
    }
    //  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;
    }
    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);
        tree.insert(14);
        tree.insert(6);
        Console.Write("\n Constructing Binomial Heap \n");
        /*
        Constructing of Binomial Heap
        ==========================
        6-------10 -----------  1
               / |            / | \   
             14  |           /  |  \
             |   12         3   4   7
             21            / \  |
                          /   \ |
                          5   9 11
                          |
                          |
                          6
        ==========================
        Logical view    
        */
        tree.printTree(tree.root);
        Console.Write("\n Minimum node : " + tree.minimum() + " ");
    }
}

Output

 Constructing Binomial Heap
  6  10  14  21  12  1  3  5  6  9  4  11  7
 Minimum node : 1
<?php
/*
    Php program 
    Construct Binomial Heap
*/
//  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;
        }
    }
    //  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;
    }
}

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);
    $tree->insert(14);
    $tree->insert(6);
    echo "\n Constructing Binomial Heap \n";
    /*
    Constructing of Binomial Heap
    ==========================
    6-------10 -----------  1
           / |            / | \   
         14  |           /  |  \
         |   12         3   4   7
         21            / \  |
                      /   \ |
                      5   9 11
                      |
                      |
                      6
    ==========================
    Logical view    
    */
    $tree->printTree($tree->root);
    echo "\n Minimum node : ". $tree->minimum() ." ";
}
main();

Output

 Constructing Binomial Heap
  6  10  14  21  12  1  3  5  6  9  4  11  7
 Minimum node : 1
/*
    Node Js program 
    Construct Binomial Heap
*/
//  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;
        }
    }
    //  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;
    }
}

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);
    tree.insert(14);
    tree.insert(6);
    process.stdout.write("\n Constructing Binomial Heap \n");
    /*
    Constructing of Binomial Heap
    ==========================
    6-------10 -----------  1
           / |            / | \   
         14  |           /  |  \
         |   12         3   4   7
         21            / \  |
                      /   \ |
                      5   9 11
                      |
                      |
                      6
    ==========================
    Logical view    
    */
    tree.printTree(tree.root);
    process.stdout.write("\n Minimum node : " + tree.minimum() + " ");
}
main();

Output

 Constructing Binomial Heap
  6  10  14  21  12  1  3  5  6  9  4  11  7
 Minimum node : 1
#  Python 3 program 
#  Construct Binomial Heap

#  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
		
	
	#  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
	

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)
	tree.insert(14)
	tree.insert(6)
	print("\n Constructing Binomial Heap ")
	# 
	# 		Constructing of Binomial Heap
	# 		==========================
	# 		6-------10 -----------  1
	# 		       / |            / | \   
	# 		     14  |           /  |  \
	# 		     |   12         3   4   7
	# 		     21            / \  |
	# 		                  /   \ |
	# 		                  5   9 11
	# 		                  |
	# 		                  |
	# 		                  6
	# 		==========================
	# 		Logical view    
	# 		
	
	tree.printTree(tree.root)
	print("\n Minimum node : ", tree.minimum() )

if __name__ == "__main__": main()

Output

 Constructing Binomial Heap
   6   10   14   21   12   1   3   5   6   9   4   11   7
 Minimum node :  1
#  Ruby program 
#  Construct Binomial Heap

#  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

	#  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

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)
	tree.insert(14)
	tree.insert(6)
	print("\n Constructing Binomial Heap \n")
	# 
	# 		Constructing of Binomial Heap
	# 		==========================
	# 		6-------10 -----------  1
	# 		       / |            / | \   
	# 		     14  |           /  |  \
	# 		     |   12         3   4   7
	# 		     21            / \  |
	# 		                  /   \ |
	# 		                  5   9 11
	# 		                  |
	# 		                  |
	# 		                  6
	# 		==========================
	# 		Logical view    
	# 		
	
	tree.printTree(tree.root)
	print("\n Minimum node : ", tree.minimum() ," ")
end

main()

Output

 Constructing Binomial Heap 
  6  10  14  21  12  1  3  5  6  9  4  11  7
 Minimum node : 1 
/*
    Scala program 
    Construct Binomial Heap
*/
//  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;
        }
    }
    //  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;
    }
}
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);
        tree.insert(14);
        tree.insert(6);
        print("\n Constructing Binomial Heap \n");
        /*
        Constructing of Binomial Heap
        ==========================
        6-------10 -----------  1
               / |            / | \   
             14  |           /  |  \
             |   12         3   4   7
             21            / \  |
                          /   \ |
                          5   9 11
                          |
                          |
                          6
        ==========================
        Logical view    
        */
        tree.printTree(tree.root);
        print("\n Minimum node : " + tree.minimum() + " ");
    }
}

Output

 Constructing Binomial Heap
  6  10  14  21  12  1  3  5  6  9  4  11  7
 Minimum node : 1
/*
    Swift 4 program 
    Construct Binomial Heap
*/
//  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;
        }
    }
    //  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;
    }
}
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);
    tree.insert(14);
    tree.insert(6);
    print("\n Constructing Binomial Heap \n", terminator: "");
    /*
    Constructing of Binomial Heap
    ==========================
    6-------10 -----------  1
           / |            / | \   
         14  |           /  |  \
         |   12         3   4   7
         21            / \  |
                      /   \ |
                      5   9 11
                      |
                      |
                      6
    ==========================
    Logical view    
    */
    tree.printTree(tree.root);
    print("\n Minimum node : ", tree.minimum() ," ", terminator: "");
}
main();

Output

 Constructing Binomial Heap
   6   10   14   21   12   1   3   5   6   9   4   11   7
 Minimum node :  1
/*
    Kotlin program 
    Construct Binomial Heap
*/
//  Define TreeNode
class TreeNode
{
    var key: Int;
    var counter: Int;
    var sibling: TreeNode?;
    var parent: TreeNode?;
    var child: TreeNode?;
    constructor(key: Int, sibling: TreeNode?)
    {
        this.key = key;
        this.sibling = sibling;
        //  Set default value of node
        this.child = null;
        this.parent = null;
        this.counter = 0;
    }
}
//  Define BinomialHeap
class BinomialHeap
{
    var root: TreeNode?;
    constructor()
    {
        this.root = null;
    }
    //  Determine that whether the given node and next sibling tree have same number of children nodes
    fun isCombine(node: TreeNode): Boolean
    {
      
        val sibling : TreeNode? = node.sibling;
        if ( sibling != null  && node.counter == sibling.counter)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    //  This is attack child tree into parent tree
    fun 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
    fun merge(node1: TreeNode, node2 : TreeNode): TreeNode
    {
       
        var temp: TreeNode ;
        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
    fun insert(key: Int): Unit
    {
        //  Create new node of tree
        var node: TreeNode = 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;
        }
    }
    //  In-order view of Binomial Heap from left to right in top tree
    fun 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
    fun minimum(): Int
    {
        if (this.root == null)
        {
            //  When empty tree
            return -1;
        }
        else
        {
          var auxiliary: TreeNode?= this.root;
          var result: Int = 0;
          if(auxiliary!=null)
          {
            result = auxiliary.key; 
          }
          //  Find last node
          while (auxiliary != null)
          {
              if (result > auxiliary.key)
              {
                  result = auxiliary.key;
              }
              auxiliary = auxiliary.sibling;
          }
          return result;
        }
       
    }
}
fun main(args: Array < String > ): Unit
{
    var 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);
    tree.insert(14);
    tree.insert(6);
    print("\n Constructing Binomial Heap \n");
    /*
    Constructing of Binomial Heap
    ==========================
    6-------10 -----------  1
           / |            / | \   
         14  |           /  |  \
         |   12         3   4   7
         21            / \  |
                      /   \ |
                      5   9 11
                      |
                      |
                      6
    ==========================
    Logical view    
    */
    tree.printTree(tree.root);
    print("\n Minimum node : " + tree.minimum() + " ");
}

Output

 Constructing Binomial Heap
  6  10  14  21  12  1  3  5  6  9  4  11  7
 Minimum node : 1

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