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