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