Binary Min Heap Tree Node Deletion
Here given code implementation process.
/*
C++ Program
Binary Min Heap Tree Node Deletion
*/
#include<iostream>
using namespace std;
class Node {
public:
Node *left;
Node *right;
int key;
Node(int value) {
this->key = value;
this->left = NULL;
this->right = NULL;
}
};
class MinHeap {
public:
int size;
Node *root;
MinHeap() {
this->root = NULL;
this->size = 0;
}
int treeHeight() {
int i = 1;
int sum = 0;
while (this->size > sum + (1 << i)) {
sum += (1 << i);
i++;
}
return i;
}
void swapNode(Node *first, Node *second) {
int temp = first->key;
first->key = second->key;
second->key = temp;
}
void arrangeNode(Node *head) {
if (head->left != NULL && head->left->key < head->key) {
this->swapNode(head, head->left);
}
if (head->right != NULL && head->right->key < head->key) {
this->swapNode(head, head->right);
}
}
bool addNode(Node *head, int height, int level, int value) {
if (level >= height) {
return false;
}
if (head != NULL) {
if (level - 1 == height && head->left == NULL || head->right == NULL) {
if (head->left == NULL) {
head->left = new Node(value);
} else {
head->right = new Node(value);
}
this->arrangeNode(head);
return true;
}
if (this->addNode(head->left, height, level + 1, value) || this->addNode(head->right, height, level + 1, value)) {
this->arrangeNode(head);
return true;
}
}
return false;
}
void insert(int value) {
if (this->root == NULL) {
this->root = new Node(value);
} else
if (this->root->left == NULL) {
this->root->left = new Node(value);
this->arrangeNode(this->root);
} else
if (this->root->right == NULL) {
this->root->right = new Node(value);
this->arrangeNode(this->root);
} else {
int height = this->treeHeight();
this->addNode(this->root, height, 0, value);
}
this->size++;
}
void preorder(Node *head) {
if (head != NULL) {
cout << " " << head->key;
this->preorder(head->left);
this->preorder(head->right);
}
}
Node *nodeParent(Node *head, int value) {
if (head != NULL) {
if (head->left != NULL && head->left->key == value || head->right != NULL && head->right->key == value) {
return head;
}
Node *element = this->nodeParent(head->left, value);
if (element == NULL) {
element = this->nodeParent(head->right, value);
}
return element;
}
return head;
}
Node *lastParent(Node *head, int height, int level) {
if (head != NULL) {
if (level == height - 1 && (head->left != NULL || head->right != NULL)) {
return head;
}
Node *element = this->lastParent(head->right, height, level + 1);
if (element == NULL) {
element = this->lastParent(head->left, height, level + 1);
}
return element;
}
return head;
}
bool isMinHeap(Node *head) {
if ((head->left != NULL && head->left->key < head->key) || (head->right != NULL && head->right->key < head->key)) {
return false;
}
return true;
}
void updateDeletion(Node *find_node) {
while (find_node != NULL) {
if (this->isMinHeap(find_node) == false) {
if (find_node->left != NULL && find_node->right != NULL) {
if (find_node->left->key < find_node->right->key) {
this->swapNode(find_node, find_node->left);
find_node = find_node->left;
} else {
this->swapNode(find_node, find_node->right);
find_node = find_node->right;
}
} else
if (find_node->right != NULL) {
this->swapNode(find_node, find_node->right);
find_node = find_node->right;
} else {
this->swapNode(find_node, find_node->left);
find_node = find_node->left;
}
} else {
break;
}
}
}
void deleteNode(int value) {
if (this->root != NULL) {
Node *find_node = NULL;
Node *last_root = NULL;
if (this->root->key == value) {
if (this->root->left == NULL && this->root->right == NULL) {
this->root = NULL;
} else
if (this->root->key == value && this->root->right == NULL) {
find_node = this->root;
this->root = this->root->left;
find_node = NULL;
} else {
int height = this->treeHeight();
if ((1 << height) - 1 == this->size) {
height--;
}
last_root = this->lastParent(this->root, height, 0);
if (last_root != NULL) {
if (last_root->right != NULL) {
this->root->key = last_root->right->key;
last_root->right = NULL;
} else
if (last_root->left != NULL) {
this->root->key = last_root->left->key;
last_root->left = NULL;
} else {
this->root->key = last_root->key;
}
this->updateDeletion(this->root);
}
}
cout << "\nDelete Node key : " << value << "\n";
this->preorder(this->root);
this->size--;
} else {
find_node = this->nodeParent(this->root, value);
if (find_node == NULL) {
cout << "\nDelete key " << value << " not exist ";
} else {
int height = this->treeHeight();
if ((1 << height) - 1 == this->size) {
height--;
}
last_root = this->lastParent(this->root, height, 0);
if (last_root != NULL) {
if (last_root == find_node) {
if (last_root->right != NULL && last_root->right->key == value) {
last_root->right = NULL;
} else
if (last_root->left != NULL && last_root->left->key == value) {
if (last_root->right != NULL) {
this->swapNode(last_root->right, last_root->left);
last_root->right = NULL;
} else {
last_root->left = NULL;
}
}
} else {
if (find_node->right != NULL && find_node->right->key == value) {
find_node = find_node->right;
} else {
find_node = find_node->left;
}
if (last_root->right != NULL) {
find_node->key = last_root->right->key;
last_root->right = NULL;
} else
if (last_root->left != NULL) {
find_node->key = last_root->left->key;
last_root->left = NULL;
} else {
find_node->key = last_root->key;
}
}
this->updateDeletion(find_node);
cout << "\nDelete Node key : " << value << "\n";
this->preorder(this->root);
this->size--;
}
}
}
} else {
cout << "Empty Min heap";
}
}
};
int main() {
MinHeap obj;
obj.insert(5);
obj.insert(7);
obj.insert(4);
obj.insert(3);
obj.insert(9);
obj.insert(14);
obj.insert(2);
obj.insert(1);
obj.insert(6);
obj.insert(11);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 9 14 5
/ \ /
7 6 11
*/
obj.preorder(obj.root);
obj.deleteNode(1);
/*
when delete node 1
//first replace last node value to root node
11
/ \
2 3
/ \ / \
4 9 14 5
/ \
7 6
//final view to arrange node value
2
/ \
4 3
/ \ / \
6 9 14 5
/ \
7 11
*/
obj.deleteNode(2);
/*
when delete node 2
11
/ \
4 3
/ \ / \
6 9 14 5
/
7
3
/ \
4 5
/ \ / \
6 9 14 11
/
7
*/
obj.deleteNode(4);
/*
when delete node 4
3
/ \
6 5
/ \ / \
7 9 14 11
*/
obj.deleteNode(14);
/*
when delete node 14
3
/ \
6 5
/ \ / \
7 9 14 11
*/
//when node are not exist
obj.deleteNode(15);
return 0;
}
Output
1 2 4 7 6 9 11 3 14 5
Delete Node key : 1
2 4 6 7 11 9 3 14 5
Delete Node key : 2
3 4 6 7 9 5 14 11
Delete Node key : 4
3 6 7 9 5 14 11
Delete Node key : 14
3 6 7 9 5 11
Delete key 15 not exist /*
Java program
Binary Min Heap Tree Node Deletion
*/
class Node {
public Node left;
public Node right;
public int key;
public Node(int value) {
key = value;
left = null;
right = null;
}
}
public class MinHeap {
//This is use to store information of number of nodes in Min heap
public int size;
public Node root;
public MinHeap() {
root = null;
size = 0;
}
//Get height of insert new node
public int treeHeight()
{
int i=1;
int sum=0;
while(this.size > sum+(1<<i) )
{
sum += (1<<i);
i++;
}
return i;
}
//Interchange the two node value
public void swapNode(Node first, Node second) {
int temp = first.key;
first.key = second.key;
second.key = temp;
}
//Arrange node key
public void arrangeNode(Node head) {
if (head.left != null && head.left.key < head.key) {
swapNode(head, head.left);
}
if (head.right != null && head.right.key < head.key) {
swapNode(head, head.right);
}
}
public boolean addNode(Node head, int height, int level, int value) {
if (level >= height) {
return false;
}
if (head != null) {
if (level - 1 == height && head.left == null || head.right == null) {
if (head.left == null) {
head.left = new Node(value);
} else {
head.right = new Node(value);
}
arrangeNode(head);
return true;
}
if (addNode(head.left, height, level + 1, value) || addNode(head.right, height, level + 1, value)) {
//Check effect of new inserted node
arrangeNode(head);
return true;
}
}
return false;
}
//Handles the request to new inserting node
public void insert(int value) {
if (root == null) {
root = new Node(value);
} else if (root.left == null) {
root.left = new Node(value);
arrangeNode(root);
} else if (root.right == null) {
root.right = new Node(value);
arrangeNode(root);
} else {
int height = treeHeight();
addNode(root, height, 0, value);
}
this.size++;
}
public void preorder(Node head) {
if (head != null) {
System.out.print(" " + head.key);
preorder(head.left);
preorder(head.right);
}
}
public Node nodeParent(Node head,int value)
{
if(head != null)
{
if(head.left != null && head.left.key == value ||
head.right != null && head.right.key == value)
{
return head;
}
Node element = nodeParent(head.left,value);
if(element==null)
{
element = nodeParent(head.right,value);
}
return element;
}
return head;
}
//Find last node of tree
public Node lastParent(Node head, int height ,int level)
{
if(head != null)
{
if(level == height-1 && (head.left!=null || head.right != null))
{
return head;
}
Node element = lastParent(head.right,height,level+1);
if(element == null)
{
element = lastParent(head.left,height,level+1);
}
return element;
}
return head;
}
public boolean isMinHeap(Node head)
{
if( (head.left!=null && head.left.key < head.key)
|| (head.right!=null && head.right.key < head.key))
{
return false;
}
return true;
}
public void updateDeletion(Node find_node)
{
//Find the new changes to make new Min heap
//O(long h)
while(find_node!=null)
{
//Check Min heap properties
if(isMinHeap(find_node)==false)
{
//fail Min heap
if(find_node.left!=null && find_node.right!=null)
{
//Repace data with Minimum value
if(find_node.left.key < find_node.right.key)
{
swapNode(find_node,find_node.left);
find_node=find_node.left;
}
else
{
swapNode(find_node,find_node.right);
find_node=find_node.right;
}
}
else if(find_node.right!=null)
{
swapNode(find_node,find_node.right);
find_node=find_node.right;
}
else
{
swapNode(find_node,find_node.left);
find_node=find_node.left;
}
}
else
{
break;
}
}
}
public void deleteNode(int value)
{
if(root!=null)
{
Node find_node = null;
Node last_root = null;
if(root.key==value )
{
if( root.left==null && root.right == null)
{
//Delete root node
root=null;
}
else if(root.key == value && root.right==null)
{
//Only two node in Min heap
find_node = root;
root = root.left;
find_node = null;
}
else
{
//Find the Min height by using tree node size
int height = treeHeight();
if((1<<height)-1==this.size)
{
//in case given height is a perfect of all leaf
height--;
}
//Find parent of a last node of tree
last_root = lastParent(root,height, 0);
if(last_root!=null)
{
//updtae key value
if(last_root.right != null)
{
root.key = last_root.right.key;
//remove last node
last_root.right = null;
}
else if(last_root.left != null)
{
root.key = last_root.left.key;
//remove last node
last_root.left = null;
}
else
{
root.key = last_root.key;
}
updateDeletion(root);
}
}
System.out.print("\nDelete Node key : "+value+"\n");
preorder(root);
//modify tree node size
this.size--;
}
else
{
//When root node is not a part of delete node
//Find parent of a delete node key
find_node = nodeParent(root,value);
if(find_node==null)
{
//In case delete node not exist
System.out.print("\nDelete key "+value+" not exist ");
}
else
{
//Find the Min height by using tree node size
int height = treeHeight();
if((1<<height)-1 == this.size)
{
//In case given height is a same of all leaf
height--;
}
//Find parent of a last node of tree
last_root = lastParent(root,height, 0);
if(last_root != null )
{
if(last_root == find_node)
{
if(last_root.right!=null && last_root.right.key==value)
{
last_root.right = null;
}
else if(last_root.left!=null && last_root.left.key==value)
{
if(last_root.right!=null)
{
swapNode(last_root.right,last_root.left);
last_root.right = null;
}
else
{
last_root.left = null;
}
}
}
else
{
//Get actual delete node location
if(find_node.right != null && find_node.right.key == value)
{
find_node=find_node.right;
}
else
{
find_node=find_node.left;
}
//Updtae key value
if(last_root.right != null)
{
find_node.key = last_root.right.key;
//remove last node
last_root.right = null;
}
else if(last_root.left != null)
{
find_node.key = last_root.left.key;
//remove last node
last_root.left = null;
}
else
{
find_node.key = last_root.key;
}
}
updateDeletion(find_node);
System.out.print("\nDelete Node key : "+value+"\n");
preorder(root);
//modify tree node size
this.size--;
}
}
}
}
else
{
System.out.println("Empty Min heap");
}
}
public static void main(String[] args) {
MinHeap obj= new MinHeap();
//Construct first Min heap tree
obj.insert(5);
obj.insert(7);
obj.insert(4);
obj.insert(3);
obj.insert(9);
obj.insert(14);
obj.insert(2);
obj.insert(1);
obj.insert(6);
obj.insert(11);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 9 14 5
/ \ /
7 6 11
*/
obj.preorder(obj.root);
obj.deleteNode(1);
/*
when delete node 1
//first replace last node value to root node
11
/ \
2 3
/ \ / \
4 9 14 5
/ \
7 6
//final view to arrange node value
2
/ \
4 3
/ \ / \
6 9 14 5
/ \
7 11
*/
obj.deleteNode(2);
/*
when delete node 2
11
/ \
4 3
/ \ / \
6 9 14 5
/
7
3
/ \
4 5
/ \ / \
6 9 14 11
/
7
*/
obj.deleteNode(4);
/*
when delete node 4
3
/ \
6 5
/ \ / \
7 9 14 11
*/
obj.deleteNode(14);
/*
when delete node 14
3
/ \
6 5
/ \ / \
7 9 14 11
*/
//when node are not exist
obj.deleteNode(15);
}
}
Output
1 2 4 7 6 9 11 3 14 5
Delete Node key : 1
2 4 6 7 11 9 3 14 5
Delete Node key : 2
3 4 6 7 9 5 14 11
Delete Node key : 4
3 6 7 9 5 14 11
Delete Node key : 14
3 6 7 9 5 11
Delete key 15 not exist /*
C# program
Binary Min Heap Tree Node Deletion
*/
using System;
public class Node {
public Node left;
public Node right;
public int key;
public Node(int value) {
key = value;
left = null;
right = null;
}
}
public class MinHeap {
//This is use to store information of number of nodes in Min heap
public int size;
public Node root;
public MinHeap() {
root = null;
size = 0;
}
//Get height of insert new node
public int treeHeight()
{
int i=1;
int sum=0;
while(this.size > sum+(1<<i) )
{
sum += (1<<i);
i++;
}
return i;
}
//Interchange the two node value
public void swapNode(Node first, Node second) {
int temp = first.key;
first.key = second.key;
second.key = temp;
}
//Arrange node key
public void arrangeNode(Node head) {
if (head.left != null && head.left.key < head.key) {
swapNode(head, head.left);
}
if (head.right != null && head.right.key < head.key) {
swapNode(head, head.right);
}
}
public Boolean addNode(Node head, int height, int level, int value) {
if (level >= height) {
return false;
}
if (head != null) {
if (level - 1 == height && head.left == null || head.right == null) {
if (head.left == null) {
head.left = new Node(value);
} else {
head.right = new Node(value);
}
arrangeNode(head);
return true;
}
if (addNode(head.left, height, level + 1, value) || addNode(head.right, height, level + 1, value)) {
//Check effect of new inserted node
arrangeNode(head);
return true;
}
}
return false;
}
//Handles the request to new inserting node
public void insert(int value) {
if (root == null) {
root = new Node(value);
} else if (root.left == null) {
root.left = new Node(value);
arrangeNode(root);
} else if (root.right == null) {
root.right = new Node(value);
arrangeNode(root);
} else {
int height = treeHeight();
addNode(root, height, 0, value);
}
this.size++;
}
public void preorder(Node head) {
if (head != null) {
Console.Write(" " + head.key);
preorder(head.left);
preorder(head.right);
}
}
public Node nodeParent(Node head,int value)
{
if(head != null)
{
if(head.left != null && head.left.key == value ||
head.right != null && head.right.key == value)
{
return head;
}
Node element = nodeParent(head.left,value);
if(element==null)
{
element = nodeParent(head.right,value);
}
return element;
}
return head;
}
//Find last node of tree
public Node lastParent(Node head, int height ,int level)
{
if(head != null)
{
if(level == height-1 && (head.left!=null || head.right != null))
{
return head;
}
Node element = lastParent(head.right,height,level+1);
if(element == null)
{
element = lastParent(head.left,height,level+1);
}
return element;
}
return head;
}
public Boolean isMinHeap(Node head)
{
if( (head.left!=null && head.left.key < head.key)
|| (head.right!=null && head.right.key < head.key))
{
return false;
}
return true;
}
public void updateDeletion(Node find_node)
{
//Find the new changes to make new Min heap
//O(long h)
while(find_node!=null)
{
//Check Min heap properties
if(isMinHeap(find_node)==false)
{
//fail Min heap
if(find_node.left!=null && find_node.right!=null)
{
//Repace data with Minimum value
if(find_node.left.key < find_node.right.key)
{
swapNode(find_node,find_node.left);
find_node=find_node.left;
}
else
{
swapNode(find_node,find_node.right);
find_node=find_node.right;
}
}
else if(find_node.right!=null)
{
swapNode(find_node,find_node.right);
find_node=find_node.right;
}
else
{
swapNode(find_node,find_node.left);
find_node=find_node.left;
}
}
else
{
break;
}
}
}
public void deleteNode(int value)
{
if(root!=null)
{
Node find_node = null;
Node last_root = null;
if(root.key==value )
{
if( root.left==null && root.right == null)
{
//Delete root node
root=null;
}
else if(root.key == value && root.right==null)
{
//Only two node in Min heap
find_node = root;
root = root.left;
find_node = null;
}
else
{
//Find the Min height by using tree node size
int height = treeHeight();
if((1<<height)-1==this.size)
{
//in case given height is a perfect of all leaf
height--;
}
//Find parent of a last node of tree
last_root = lastParent(root,height, 0);
if(last_root!=null)
{
//updtae key value
if(last_root.right != null)
{
root.key = last_root.right.key;
//remove last node
last_root.right = null;
}
else if(last_root.left != null)
{
root.key = last_root.left.key;
//remove last node
last_root.left = null;
}
else
{
root.key = last_root.key;
}
updateDeletion(root);
}
}
Console.Write("\nDelete Node key : "+value+"\n");
preorder(root);
//modify tree node size
this.size--;
}
else
{
//When root node is not a part of delete node
//Find parent of a delete node key
find_node = nodeParent(root,value);
if(find_node==null)
{
//In case delete node not exist
Console.Write("\nDelete key "+value+" not exist ");
}
else
{
//Find the Min height by using tree node size
int height = treeHeight();
if((1<<height)-1 == this.size)
{
//In case given height is a same of all leaf
height--;
}
//Find parent of a last node of tree
last_root = lastParent(root,height, 0);
if(last_root != null )
{
if(last_root == find_node)
{
if(last_root.right!=null && last_root.right.key==value)
{
last_root.right = null;
}
else if(last_root.left!=null && last_root.left.key==value)
{
if(last_root.right!=null)
{
swapNode(last_root.right,last_root.left);
last_root.right = null;
}
else
{
last_root.left = null;
}
}
}
else
{
//Get actual delete node location
if(find_node.right != null && find_node.right.key == value)
{
find_node=find_node.right;
}
else
{
find_node=find_node.left;
}
//Updtae key value
if(last_root.right != null)
{
find_node.key = last_root.right.key;
//remove last node
last_root.right = null;
}
else if(last_root.left != null)
{
find_node.key = last_root.left.key;
//remove last node
last_root.left = null;
}
else
{
find_node.key = last_root.key;
}
}
updateDeletion(find_node);
Console.Write("\nDelete Node key : "+value+"\n");
preorder(root);
//modify tree node size
this.size--;
}
}
}
}
else
{
Console.WriteLine("Empty Min heap");
}
}
public static void Main(String[] args) {
MinHeap obj= new MinHeap();
//Construct first Min heap tree
obj.insert(5);
obj.insert(7);
obj.insert(4);
obj.insert(3);
obj.insert(9);
obj.insert(14);
obj.insert(2);
obj.insert(1);
obj.insert(6);
obj.insert(11);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 9 14 5
/ \ /
7 6 11
*/
obj.preorder(obj.root);
obj.deleteNode(1);
/*
when delete node 1
//first replace last node value to root node
11
/ \
2 3
/ \ / \
4 9 14 5
/ \
7 6
//final view to arrange node value
2
/ \
4 3
/ \ / \
6 9 14 5
/ \
7 11
*/
obj.deleteNode(2);
/*
when delete node 2
11
/ \
4 3
/ \ / \
6 9 14 5
/
7
3
/ \
4 5
/ \ / \
6 9 14 11
/
7
*/
obj.deleteNode(4);
/*
when delete node 4
3
/ \
6 5
/ \ / \
7 9 14 11
*/
obj.deleteNode(14);
/*
when delete node 14
3
/ \
6 5
/ \ / \
7 9 14 11
*/
//when node are not exist
obj.deleteNode(15);
}
}
Output
1 2 4 7 6 9 11 3 14 5
Delete Node key : 1
2 4 6 7 11 9 3 14 5
Delete Node key : 2
3 4 6 7 9 5 14 11
Delete Node key : 4
3 6 7 9 5 14 11
Delete Node key : 14
3 6 7 9 5 11
Delete key 15 not exist # Python 3 Program
# Binary Min Heap Tree Node Deletion
class Node :
def __init__(self, value) :
self.key = value
self.left = None
self.right = None
class MinHeap :
def __init__(self) :
self.root = None
self.size = 0
def treeHeight(self) :
i = 1
sum = 0
while (self.size > sum + (1 << i)) :
sum += (1 << i)
i += 1
return i
def swapNode(self, first, second) :
temp = first.key
first.key = second.key
second.key = temp
def arrangeNode(self, head) :
if (head.left != None and head.left.key < head.key) :
self.swapNode(head, head.left)
if (head.right != None and head.right.key < head.key) :
self.swapNode(head, head.right)
def addNode(self, head, height, level, value) :
if (level >= height) :
return False
if (head != None) :
if (level - 1 == height and head.left == None or head.right == None) :
if (head.left == None) :
head.left = Node(value)
else :
head.right = Node(value)
self.arrangeNode(head)
return True
if (self.addNode(head.left, height, level + 1, value) or self.addNode(head.right, height, level + 1, value)) :
self.arrangeNode(head)
return True
return False
def insert(self, value) :
if (self.root == None) :
self.root = Node(value)
elif (self.root.left == None) :
self.root.left = Node(value)
self.arrangeNode(self.root)
elif (self.root.right == None) :
self.root.right = Node(value)
self.arrangeNode(self.root)
else :
height = self.treeHeight()
self.addNode(self.root, height, 0, value)
self.size += 1
def preorder(self, head) :
if (head != None) :
print(" ", head.key,end="")
self.preorder(head.left)
self.preorder(head.right)
def nodeParent(self, head, value) :
if (head != None) :
if (head.left != None and head.left.key == value or head.right != None and head.right.key == value) :
return head
element = self.nodeParent(head.left, value)
if (element == None) :
element = self.nodeParent(head.right, value)
return element
return head
def lastParent(self, head, height, level) :
if (head != None) :
if (level == height - 1 and(head.left != None or head.right != None)) :
return head
element = self.lastParent(head.right, height, level + 1)
if (element == None) :
element = self.lastParent(head.left, height, level + 1)
return element
return head
def isMinHeap(self, head) :
if ((head.left != None and head.left.key < head.key) or(head.right != None and head.right.key < head.key)) :
return False
return True
def updateDeletion(self, find_node) :
while (find_node != None) :
if (self.isMinHeap(find_node) == False) :
if (find_node.left != None and find_node.right != None) :
if (find_node.left.key < find_node.right.key) :
self.swapNode(find_node, find_node.left)
find_node = find_node.left
else :
self.swapNode(find_node, find_node.right)
find_node = find_node.right
elif (find_node.right != None) :
self.swapNode(find_node, find_node.right)
find_node = find_node.right
else :
self.swapNode(find_node, find_node.left)
find_node = find_node.left
else :
break
def deleteNode(self, value) :
if (self.root != None) :
find_node = None
last_root = None
if (self.root.key == value) :
if (self.root.left == None and self.root.right == None) :
self.root = None
elif (self.root.key == value and self.root.right == None) :
find_node = self.root
self.root = self.root.left
find_node = None
else :
height = self.treeHeight()
if ((1 << height) - 1 == self.size) :
height -= 1
last_root = self.lastParent(self.root, height, 0)
if (last_root != None) :
if (last_root.right != None) :
self.root.key = last_root.right.key
last_root.right = None
elif (last_root.left != None) :
self.root.key = last_root.left.key
last_root.left = None
else :
self.root.key = last_root.key
self.updateDeletion(self.root)
print("\nDelete Node key : ", value )
self.preorder(self.root)
self.size -= 1
else :
find_node = self.nodeParent(self.root, value)
if (find_node == None) :
print("\nDelete key ", value ," not exist ")
else :
height = self.treeHeight()
if ((1 << height) - 1 == self.size) :
height -= 1
last_root = self.lastParent(self.root, height, 0)
if (last_root != None) :
if (last_root == find_node) :
if (last_root.right != None and last_root.right.key == value) :
last_root.right = None
elif (last_root.left != None and last_root.left.key == value) :
if (last_root.right != None) :
self.swapNode(last_root.right, last_root.left)
last_root.right = None
else :
last_root.left = None
else :
if (find_node.right != None and find_node.right.key == value) :
find_node = find_node.right
else :
find_node = find_node.left
if (last_root.right != None) :
find_node.key = last_root.right.key
last_root.right = None
elif (last_root.left != None) :
find_node.key = last_root.left.key
last_root.left = None
else :
find_node.key = last_root.key
self.updateDeletion(find_node)
print("\nDelete Node key : ", value )
self.preorder(self.root)
self.size -= 1
else :
print("Empty Min heap")
def main() :
obj = MinHeap()
obj.insert(5)
obj.insert(7)
obj.insert(4)
obj.insert(3)
obj.insert(9)
obj.insert(14)
obj.insert(2)
obj.insert(1)
obj.insert(6)
obj.insert(11)
# After insert element
#
# 1
# / \
# 2 3
# / \ / \
# 4 9 14 5
# / \ /
# 7 6 11
#
obj.preorder(obj.root)
obj.deleteNode(1)
#
# when delete node 1
# first replace last node value to root node
# 11
# / \
# 2 3
# / \ / \
# 4 9 14 5
# / \
# 7 6
# final view to arrange node value
# 2
# / \
# 4 3
# / \ / \
# 6 9 14 5
# / \
# 7 11
#
obj.deleteNode(2)
#
# when delete node 2
# 11
# / \
# 4 3
# / \ / \
# 6 9 14 5
# /
# 7
# 3
# / \
# 4 5
# / \ / \
# 6 9 14 11
# /
# 7
#
obj.deleteNode(4)
#
# when delete node 4
# 3
# / \
# 6 5
# / \ / \
# 7 9 14 11
#
obj.deleteNode(14)
#
# when delete node 14
# 3
# / \
# 6 5
# / \ / \
# 7 9 14 11
#
#when node are not exist
obj.deleteNode(15)
if __name__ == "__main__":
main()
Output
1 2 4 7 6 9 11 3 14 5
Delete Node key : 1
2 4 6 7 11 9 3 14 5
Delete Node key : 2
3 4 6 7 9 5 14 11
Delete Node key : 4
3 6 7 9 5 14 11
Delete Node key : 14
3 6 7 9 5 11
Delete key 15 not exist # Ruby Program
# Binary Min Heap Tree Node Deletion
class Node
attr_reader :left, :right, :key
attr_accessor :left, :right, :key
def initialize(value)
@key = value
@left = nil
@right = nil
end
end
class MinHeap
attr_reader :size, :root
attr_accessor :size, :root
def initialize()
@root = nil
@size = 0
end
def treeHeight()
i = 1
sum = 0
while (self.size > sum + (1 << i))
sum += (1 << i)
i += 1
end
return i
end
def swapNode(first, second)
temp = first.key
first.key = second.key
second.key = temp
end
def arrangeNode(head)
if (head.left != nil and head.left.key < head.key)
self.swapNode(head, head.left)
end
if (head.right != nil and head.right.key < head.key)
self.swapNode(head, head.right)
end
end
def addNode(head, height, level, value)
if (level >= height)
return false
end
if (head != nil)
if (level - 1 == height and head.left == nil or head.right == nil)
if (head.left == nil)
head.left = Node.new(value)
else
head.right = Node.new(value)
end
self.arrangeNode(head)
return true
end
if (self.addNode(head.left, height, level + 1, value) or self.addNode(head.right, height, level + 1, value))
self.arrangeNode(head)
return true
end
end
return false
end
def insert(value)
if (@root == nil)
@root = Node.new(value)
elsif (@root.left == nil)
@root.left = Node.new(value)
self.arrangeNode(@root)
elsif (@root.right == nil)
@root.right = Node.new(value)
self.arrangeNode(@root)
else
height = self.treeHeight()
self.addNode(@root, height, 0, value)
end
self.size += 1
end
def preorder(head)
if (head != nil)
print(" ", head.key)
self.preorder(head.left)
self.preorder(head.right)
end
end
def nodeParent(head, value)
if (head != nil)
if ((head.left != nil and head.left.key == value) or (head.right != nil and head.right.key == value))
return head
end
element = self.nodeParent(head.left, value)
if (element == nil)
element = self.nodeParent(head.right, value)
end
return element
end
return head
end
def lastParent(head, height, level)
if (head != nil)
if (level == height - 1 and(head.left != nil or head.right != nil))
return head
end
element = self.lastParent(head.right, height, level + 1)
if (element == nil)
element = self.lastParent(head.left, height, level + 1)
end
return element
end
return head
end
def isMinHeap(head)
if ((head.left != nil and head.left.key < head.key) or(head.right != nil and head.right.key < head.key))
return false
end
return true
end
def updateDeletion(find_node)
while (find_node != nil)
if (self.isMinHeap(find_node) == false)
if (find_node.left != nil and find_node.right != nil)
if (find_node.left.key < find_node.right.key)
self.swapNode(find_node, find_node.left)
find_node = find_node.left
else
self.swapNode(find_node, find_node.right)
find_node = find_node.right
end
elsif (find_node.right != nil)
self.swapNode(find_node, find_node.right)
find_node = find_node.right
else
self.swapNode(find_node, find_node.left)
find_node = find_node.left
end
else
break
end
end
end
def deleteNode(value)
if (@root != nil)
find_node = nil
last_root = nil
if (@root.key == value)
if (@root.left == nil and @root.right == nil)
@root = nil
elsif (@root.key == value and @root.right == nil)
find_node = @root
@root = @root.left
find_node = nil
else
height = self.treeHeight()
if ((1 << height) - 1 == self.size)
height -= 1
end
last_root = self.lastParent(@root, height, 0)
if (last_root != nil)
if (last_root.right != nil)
@root.key = last_root.right.key
last_root.right = nil
elsif (last_root.left != nil)
@root.key = last_root.left.key
last_root.left = nil
else
@root.key = last_root.key
end
self.updateDeletion(@root)
end
end
print("\nDelete Node key :", value ,"\n")
self.preorder(@root)
self.size -= 1
else
find_node = self.nodeParent(@root, value)
if (find_node == nil)
print("\nDelete key ", value ," not exist ")
else
height = self.treeHeight()
if ((1 << height) - 1 == self.size)
height -= 1
end
last_root = self.lastParent(@root, height, 0)
if (last_root != nil)
if (last_root == find_node)
if (last_root.right != nil and last_root.right.key == value)
last_root.right = nil
elsif (last_root.left != nil and last_root.left.key == value)
if (last_root.right != nil)
self.swapNode(last_root.right, last_root.left)
last_root.right = nil
else
last_root.left = nil
end
end
else
if (find_node.right != nil and find_node.right.key == value)
find_node = find_node.right
else
find_node = find_node.left
end
if (last_root.right != nil)
find_node.key = last_root.right.key
last_root.right = nil
elsif (last_root.left != nil)
find_node.key = last_root.left.key
last_root.left = nil
else
find_node.key = last_root.key
end
end
self.updateDeletion(find_node)
print("\nDelete Node key :", value ,"\n")
self.preorder(@root)
self.size -= 1
end
end
end
else
print("Empty Min heap")
end
end
end
def main()
obj = MinHeap.new()
obj.insert(5)
obj.insert(7)
obj.insert(4)
obj.insert(3)
obj.insert(9)
obj.insert(14)
obj.insert(2)
obj.insert(1)
obj.insert(6)
obj.insert(11)
# After insert element
#
# 1
# / \
# 2 3
# / \ / \
# 4 9 14 5
# / \ /
# 7 6 11
#
obj.preorder(obj.root)
obj.deleteNode(1)
#
# when delete node 1
# first replace last node value to root node
# 11
# / \
# 2 3
# / \ / \
# 4 9 14 5
# / \
# 7 6
# final view to arrange node value
# 2
# / \
# 4 3
# / \ / \
# 6 9 14 5
# / \
# 7 11
#
obj.deleteNode(2)
#
# when delete node 2
# 11
# / \
# 4 3
# / \ / \
# 6 9 14 5
# /
# 7
# 3
# / \
# 4 5
# / \ / \
# 6 9 14 11
# /
# 7
#
obj.deleteNode(4)
#
# when delete node 4
# 3
# / \
# 6 5
# / \ / \
# 7 9 14 11
#
obj.deleteNode(14)
#
# when delete node 14
# 3
# / \
# 6 5
# / \ / \
# 7 9 14 11
#
#when node are not exist
obj.deleteNode(15)
end
main()
Output
1 2 4 7 6 9 11 3 14 5
Delete Node key : 1
2 4 6 7 11 9 3 14 5
Delete Node key : 2
3 4 6 7 9 5 14 11
Delete Node key : 4
3 6 7 9 5 14 11
Delete Node key : 14
3 6 7 9 5 11
Delete key 15 not exist <?php
/*
Php Program
Binary Min Heap Tree Node Deletion
*/
class Node {
public $left;
public $right;
public $key;
function __construct($value) {
$this->key = $value;
$this->left = null;
$this->right = null;
}
}
class MinHeap {
public $size;
public $root;
function __construct() {
$this->root = null;
$this->size = 0;
}
public function treeHeight() {
$i = 1;
$sum = 0;
while ($this->size > $sum + (1 << $i)) {
$sum += (1 << $i);
$i++;
}
return $i;
}
public function swapNode($first, $second) {
$temp = $first->key;
$first->key = $second->key;
$second->key = $temp;
}
public function arrangeNode($head) {
if ($head->left != null && $head->left->key < $head->key) {
$this->swapNode($head, $head->left);
}
if ($head->right != null && $head->right->key < $head->key) {
$this->swapNode($head, $head->right);
}
}
public function addNode($head, $height, $level, $value) {
if ($level >= $height) {
return false;
}
if ($head != null) {
if ($level - 1 == $height && $head->left == null || $head->right == null) {
if ($head->left == null) {
$head->left = new Node($value);
} else {
$head->right = new Node($value);
}
$this->arrangeNode($head);
return true;
}
if ($this->addNode($head->left, $height, $level + 1, $value) || $this->addNode($head->right, $height, $level + 1, $value)) {
$this->arrangeNode($head);
return true;
}
}
return false;
}
public function insert($value) {
if ($this->root == null) {
$this->root = new Node($value);
} else
if ($this->root->left == null) {
$this->root->left = new Node($value);
$this->arrangeNode($this->root);
} else
if ($this->root->right == null) {
$this->root->right = new Node($value);
$this->arrangeNode($this->root);
} else {
$height = $this->treeHeight();
$this->addNode($this->root, $height, 0, $value);
}
$this->size++;
}
public function preorder($head) {
if ($head != null) {
echo(" ". $head->key);
$this->preorder($head->left);
$this->preorder($head->right);
}
}
public function nodeParent($head, $value) {
if ($head != null) {
if ($head->left != null && $head->left->key == $value || $head->right != null && $head->right->key == $value) {
return $head;
}
$element = $this->nodeParent($head->left, $value);
if ($element == null) {
$element = $this->nodeParent($head->right, $value);
}
return $element;
}
return $head;
}
public function lastParent($head, $height, $level) {
if ($head != null) {
if ($level == $height - 1 && ($head->left != null || $head->right != null)) {
return $head;
}
$element = $this->lastParent($head->right, $height, $level + 1);
if ($element == null) {
$element = $this->lastParent($head->left, $height, $level + 1);
}
return $element;
}
return $head;
}
public function isMinHeap($head) {
if (($head->left != null && $head->left->key < $head->key) || ($head->right != null && $head->right->key < $head->key)) {
return false;
}
return true;
}
public function updateDeletion($find_node) {
while ($find_node != null) {
if ($this->isMinHeap($find_node) == false) {
if ($find_node->left != null && $find_node->right != null) {
if ($find_node->left->key < $find_node->right->key) {
$this->swapNode($find_node, $find_node->left);
$find_node = $find_node->left;
} else {
$this->swapNode($find_node, $find_node->right);
$find_node = $find_node->right;
}
} else
if ($find_node->right != null) {
$this->swapNode($find_node, $find_node->right);
$find_node = $find_node->right;
} else {
$this->swapNode($find_node, $find_node->left);
$find_node = $find_node->left;
}
} else {
break;
}
}
}
public function deleteNode($value) {
if ($this->root != null) {
$find_node = null;
$last_root = null;
if ($this->root->key == $value) {
if ($this->root->left == null && $this->root->right == null) {
$this->root = null;
} else
if ($this->root->key == $value && $this->root->right == null) {
$find_node = $this->root;
$this->root = $this->root->left;
$find_node = null;
} else {
$height = $this->treeHeight();
if ((1 << $height) - 1 == $this->size) {
$height--;
}
$last_root = $this->lastParent($this->root, $height, 0);
if ($last_root != null) {
if ($last_root->right != null) {
$this->root->key = $last_root->right->key;
$last_root->right = null;
} else
if ($last_root->left != null) {
$this->root->key = $last_root->left->key;
$last_root->left = null;
} else {
$this->root->key = $last_root->key;
}
$this->updateDeletion($this->root);
}
}
echo("\nDelete Node key : ". $value ."\n");
$this->preorder($this->root);
$this->size--;
} else {
$find_node = $this->nodeParent($this->root, $value);
if ($find_node == null) {
echo("\nDelete key ". $value ." not exist ");
} else {
$height = $this->treeHeight();
if ((1 << $height) - 1 == $this->size) {
$height--;
}
$last_root = $this->lastParent($this->root, $height, 0);
if ($last_root != null) {
if ($last_root == $find_node) {
if ($last_root->right != null && $last_root->right->key == $value) {
$last_root->right = null;
} else
if ($last_root->left != null && $last_root->left->key == $value) {
if ($last_root->right != null) {
$this->swapNode($last_root->right, $last_root->left);
$last_root->right = null;
} else {
$last_root->left = null;
}
}
} else {
if ($find_node->right != null && $find_node->right->key == $value) {
$find_node = $find_node->right;
} else {
$find_node = $find_node->left;
}
if ($last_root->right != null) {
$find_node->key = $last_root->right->key;
$last_root->right = null;
} else
if ($last_root->left != null) {
$find_node->key = $last_root->left->key;
$last_root->left = null;
} else {
$find_node->key = $last_root->key;
}
}
$this->updateDeletion($find_node);
echo("\nDelete Node key : ". $value ."\n");
$this->preorder($this->root);
$this->size--;
}
}
}
} else {
echo("Empty Min heap");
}
}
}
function main() {
$obj = new MinHeap();
$obj->insert(5);
$obj->insert(7);
$obj->insert(4);
$obj->insert(3);
$obj->insert(9);
$obj->insert(14);
$obj->insert(2);
$obj->insert(1);
$obj->insert(6);
$obj->insert(11);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 9 14 5
/ \ /
7 6 11
*/
$obj->preorder($obj->root);
$obj->deleteNode(1);
/*
when delete node 1
//first replace last node value to root node
11
/ \
2 3
/ \ / \
4 9 14 5
/ \
7 6
//final view to arrange node value
2
/ \
4 3
/ \ / \
6 9 14 5
/ \
7 11
*/
$obj->deleteNode(2);
/*
when delete node 2
11
/ \
4 3
/ \ / \
6 9 14 5
/
7
3
/ \
4 5
/ \ / \
6 9 14 11
/
7
*/
$obj->deleteNode(4);
/*
when delete node 4
3
/ \
6 5
/ \ / \
7 9 14 11
*/
$obj->deleteNode(14);
/*
when delete node 14
3
/ \
6 5
/ \ / \
7 9 14 11
*/
//when node are not exist
$obj->deleteNode(15);
}
main();
Output
1 2 4 7 6 9 11 3 14 5
Delete Node key : 1
2 4 6 7 11 9 3 14 5
Delete Node key : 2
3 4 6 7 9 5 14 11
Delete Node key : 4
3 6 7 9 5 14 11
Delete Node key : 14
3 6 7 9 5 11
Delete key 15 not exist /*
Node Js Program
Binary Min Heap Tree Node Deletion
*/
class Node {
constructor(value) {
this.key = value;
this.left = null;
this.right = null;
}
}
class MinHeap {
constructor() {
this.root = null;
this.size = 0;
}
treeHeight() {
var i = 1;
var sum = 0;
while (this.size > sum + (1 << i)) {
sum += (1 << i);
i++;
}
return i;
}
swapNode(first, second) {
var temp = first.key;
first.key = second.key;
second.key = temp;
}
arrangeNode(head) {
if (head.left != null && head.left.key < head.key) {
this.swapNode(head, head.left);
}
if (head.right != null && head.right.key < head.key) {
this.swapNode(head, head.right);
}
}
addNode(head, height, level, value) {
if (level >= height) {
return false;
}
if (head != null) {
if (level - 1 == height && head.left == null || head.right == null) {
if (head.left == null) {
head.left = new Node(value);
} else {
head.right = new Node(value);
}
this.arrangeNode(head);
return true;
}
if (this.addNode(head.left, height, level + 1, value) || this.addNode(head.right, height, level + 1, value)) {
this.arrangeNode(head);
return true;
}
}
return false;
}
insert(value) {
if (this.root == null) {
this.root = new Node(value);
} else
if (this.root.left == null) {
this.root.left = new Node(value);
this.arrangeNode(this.root);
} else
if (this.root.right == null) {
this.root.right = new Node(value);
this.arrangeNode(this.root);
} else {
var height = this.treeHeight();
this.addNode(this.root, height, 0, value);
}
this.size++;
}
preorder(head) {
if (head != null) {
process.stdout.write(" " + head.key);
this.preorder(head.left);
this.preorder(head.right);
}
}
nodeParent(head, value) {
if (head != null) {
if (head.left != null && head.left.key == value || head.right != null && head.right.key == value) {
return head;
}
var element = this.nodeParent(head.left, value);
if (element == null) {
element = this.nodeParent(head.right, value);
}
return element;
}
return head;
}
lastParent(head, height, level) {
if (head != null) {
if (level == height - 1 && (head.left != null || head.right != null)) {
return head;
}
var element = this.lastParent(head.right, height, level + 1);
if (element == null) {
element = this.lastParent(head.left, height, level + 1);
}
return element;
}
return head;
}
isMinHeap(head) {
if ((head.left != null && head.left.key < head.key) || (head.right != null && head.right.key < head.key)) {
return false;
}
return true;
}
updateDeletion(find_node) {
while (find_node != null) {
if (this.isMinHeap(find_node) == false) {
if (find_node.left != null && find_node.right != null) {
if (find_node.left.key < find_node.right.key) {
this.swapNode(find_node, find_node.left);
find_node = find_node.left;
} else {
this.swapNode(find_node, find_node.right);
find_node = find_node.right;
}
} else
if (find_node.right != null) {
this.swapNode(find_node, find_node.right);
find_node = find_node.right;
} else {
this.swapNode(find_node, find_node.left);
find_node = find_node.left;
}
} else {
break;
}
}
}
deleteNode(value) {
if (this.root != null) {
var find_node = null;
var last_root = null;
if (this.root.key == value) {
if (this.root.left == null && this.root.right == null) {
this.root = null;
} else
if (this.root.key == value && this.root.right == null) {
find_node = this.root;
this.root = this.root.left;
find_node = null;
} else {
var height = this.treeHeight();
if ((1 << height) - 1 == this.size) {
height--;
}
last_root = this.lastParent(this.root, height, 0);
if (last_root != null) {
if (last_root.right != null) {
this.root.key = last_root.right.key;
last_root.right = null;
} else
if (last_root.left != null) {
this.root.key = last_root.left.key;
last_root.left = null;
} else {
this.root.key = last_root.key;
}
this.updateDeletion(this.root);
}
}
process.stdout.write("\nDelete Node key : " + value + "\n");
this.preorder(this.root);
this.size--;
} else {
find_node = this.nodeParent(this.root, value);
if (find_node == null) {
process.stdout.write("\nDelete key " + value + " not exist ");
} else {
var height = this.treeHeight();
if ((1 << height) - 1 == this.size) {
height--;
}
last_root = this.lastParent(this.root, height, 0);
if (last_root != null) {
if (last_root == find_node) {
if (last_root.right != null && last_root.right.key == value) {
last_root.right = null;
} else
if (last_root.left != null && last_root.left.key == value) {
if (last_root.right != null) {
this.swapNode(last_root.right, last_root.left);
last_root.right = null;
} else {
last_root.left = null;
}
}
} else {
if (find_node.right != null && find_node.right.key == value) {
find_node = find_node.right;
} else {
find_node = find_node.left;
}
if (last_root.right != null) {
find_node.key = last_root.right.key;
last_root.right = null;
} else
if (last_root.left != null) {
find_node.key = last_root.left.key;
last_root.left = null;
} else {
find_node.key = last_root.key;
}
}
this.updateDeletion(find_node);
process.stdout.write("\nDelete Node key : " + value + "\n");
this.preorder(this.root);
this.size--;
}
}
}
} else {
process.stdout.write("Empty Min heap");
}
}
}
function main() {
var obj = new MinHeap();
obj.insert(5);
obj.insert(7);
obj.insert(4);
obj.insert(3);
obj.insert(9);
obj.insert(14);
obj.insert(2);
obj.insert(1);
obj.insert(6);
obj.insert(11);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 9 14 5
/ \ /
7 6 11
*/
obj.preorder(obj.root);
obj.deleteNode(1);
/*
when delete node 1
//first replace last node value to root node
11
/ \
2 3
/ \ / \
4 9 14 5
/ \
7 6
//final view to arrange node value
2
/ \
4 3
/ \ / \
6 9 14 5
/ \
7 11
*/
obj.deleteNode(2);
/*
when delete node 2
11
/ \
4 3
/ \ / \
6 9 14 5
/
7
3
/ \
4 5
/ \ / \
6 9 14 11
/
7
*/
obj.deleteNode(4);
/*
when delete node 4
3
/ \
6 5
/ \ / \
7 9 14 11
*/
obj.deleteNode(14);
/*
when delete node 14
3
/ \
6 5
/ \ / \
7 9 14 11
*/
//when node are not exist
obj.deleteNode(15);
}
main();
Output
1 2 4 7 6 9 11 3 14 5
Delete Node key : 1
2 4 6 7 11 9 3 14 5
Delete Node key : 2
3 4 6 7 9 5 14 11
Delete Node key : 4
3 6 7 9 5 14 11
Delete Node key : 14
3 6 7 9 5 11
Delete key 15 not exist /*
Swift 4 Program
*/
class Node {
var left: Node? ;
var right: Node? ;
var key: Int;
init(_ value: Int) {
self.key = value;
self.left = nil;
self.right = nil;
}
}
class MinHeap {
var size: Int;
var root: Node? ;
init() {
self.root = nil;
self.size = 0;
}
func treeHeight() -> Int {
var i: Int = 1;
var sum: Int = 0;
while (self.size > sum + (1 << i)) {
sum += (1 << i);
i += 1;
}
return i;
}
func swapNode(_ first: Node? , _ second : Node? ) {
let temp: Int = first!.key;
first!.key = second!.key;
second!.key = temp;
}
func arrangeNode(_ head: Node? ) {
if (head!.left != nil && head!.left!.key < head!.key) {
self.swapNode(head, head!.left);
}
if (head!.right != nil && head!.right!.key < head!.key) {
self.swapNode(head, head!.right);
}
}
func addNode(_ head: Node? , _ height : Int, _ level: Int, _ value: Int) -> Bool {
if (level >= height) {
return false;
}
if (head != nil) {
if (level - 1 == height && head!.left == nil || head!.right == nil) {
if (head!.left == nil) {
head!.left = Node(value);
} else {
head!.right = Node(value);
}
self.arrangeNode(head);
return true;
}
if (self.addNode(head!.left, height, level + 1, value) || self.addNode(head!.right, height, level + 1, value)) {
self.arrangeNode(head);
return true;
}
}
return false;
}
func insert(_ value: Int) {
if (self.root == nil) {
self.root = Node(value);
} else
if (self.root!.left == nil) {
self.root!.left = Node(value);
self.arrangeNode(self.root);
} else
if (self.root!.right == nil) {
self.root!.right = Node(value);
self.arrangeNode(self.root);
} else {
let height: Int = self.treeHeight();
let _ = self.addNode(self.root, height, 0, value);
}
self.size += 1;
}
func preorder(_ head: Node? ) {
if (head != nil) {
print(" ", head!.key,terminator:"");
self.preorder(head!.left);
self.preorder(head!.right);
}
}
func nodeParent(_ head: Node? , _ value : Int) -> Node? {
if (head != nil) {
if (head!.left != nil && head!.left!.key == value || head!.right != nil && head!.right!.key == value) {
return head;
}
var element: Node? = self.nodeParent(head!.left, value);
if (element == nil) {
element = self.nodeParent(head!.right, value);
}
return element;
}
return head;
}
func lastParent(_ head: Node? , _ height : Int, _ level: Int) -> Node?{
if (head != nil) {
if (level == height - 1 && (head!.left != nil || head!.right != nil)) {
return head;
}
var element: Node? = self.lastParent(head!.right, height, level + 1);
if (element == nil) {
element = self.lastParent(head!.left, height, level + 1);
}
return element;
}
return head;
}
func isMinHeap(_ head: Node? ) -> Bool {
if ((head!.left != nil && head!.left!.key < head!.key) || (head!.right != nil && head!.right!.key < head!.key)) {
return false;
}
return true;
}
func updateDeletion(_ head: Node? ) {
var find_node: Node? = head;
while (find_node != nil) {
if (self.isMinHeap(find_node) == false) {
if (find_node!.left != nil && find_node!.right != nil) {
if (find_node!.left!.key < find_node!.right!.key) {
self.swapNode(find_node, find_node!.left);
find_node = find_node!.left;
} else {
self.swapNode(find_node, find_node!.right);
find_node = find_node!.right;
}
} else
if (find_node!.right != nil) {
self.swapNode(find_node, find_node!.right);
find_node = find_node!.right;
} else {
self.swapNode(find_node, find_node!.left);
find_node = find_node!.left;
}
} else {
break;
}
}
}
func deleteNode(_ value: Int) {
if (self.root != nil) {
var find_node: Node? = nil;
var last_root: Node? = nil;
if (self.root!.key == value) {
if (self.root!.left == nil && self.root!.right == nil) {
self.root = nil;
} else
if (self.root!.key == value && self.root!.right == nil) {
find_node = self.root;
self.root = self.root!.left;
find_node = nil;
} else {
var height: Int = self.treeHeight();
if ((1 << height) - 1 == self.size) {
height -= 1;
}
last_root = self.lastParent(self.root, height, 0);
if (last_root != nil) {
if (last_root!.right != nil) {
self.root!.key = last_root!.right!.key;
last_root!.right = nil;
} else
if (last_root!.left != nil) {
self.root!.key = last_root!.left!.key;
last_root!.left = nil;
} else {
self.root!.key = last_root!.key;
}
self.updateDeletion(self.root);
}
}
print("\nDelete Node key : ", value );
self.preorder(self.root);
self.size -= 1;
} else {
find_node = self.nodeParent(self.root, value);
if (find_node == nil) {
print("\nDelete key ", value ," not exist ");
} else {
var height: Int = self.treeHeight();
if ((1 << height) - 1 == self.size) {
height -= 1;
}
last_root = self.lastParent(self.root, height, 0);
if (last_root != nil) {
if (last_root === find_node) {
if (last_root!.right != nil && last_root!.right!.key == value) {
last_root!.right = nil;
} else
if (last_root!.left != nil && last_root!.left!.key == value) {
if (last_root!.right != nil) {
self.swapNode(last_root!.right, last_root!.left);
last_root!.right = nil;
} else {
last_root!.left = nil;
}
}
} else {
if (find_node!.right != nil && find_node!.right!.key == value) {
find_node = find_node!.right;
} else {
find_node = find_node!.left;
}
if (last_root!.right != nil) {
find_node!.key = last_root!.right!.key;
last_root!.right = nil;
} else
if (last_root!.left != nil) {
find_node!.key = last_root!.left!.key;
last_root!.left = nil;
} else {
find_node!.key = last_root!.key;
}
}
self.updateDeletion(find_node);
print("\nDelete Node key : ", value );
self.preorder(self.root);
self.size -= 1;
}
}
}
} else {
print("Empty Min heap");
}
}
}
func main() {
let obj: MinHeap = MinHeap();
obj.insert(5);
obj.insert(7);
obj.insert(4);
obj.insert(3);
obj.insert(9);
obj.insert(14);
obj.insert(2);
obj.insert(1);
obj.insert(6);
obj.insert(11);
/*After insert element*/
/*
1
/ \
2 3
/ \ / \
4 9 14 5
/ \ /
7 6 11
*/
obj.preorder(obj.root);
obj.deleteNode(1);
/*
when delete node 1
//first replace last node value to root node
11
/ \
2 3
/ \ / \
4 9 14 5
/ \
7 6
//final view to arrange node value
2
/ \
4 3
/ \ / \
6 9 14 5
/ \
7 11
*/
obj.deleteNode(2);
/*
when delete node 2
11
/ \
4 3
/ \ / \
6 9 14 5
/
7
3
/ \
4 5
/ \ / \
6 9 14 11
/
7
*/
obj.deleteNode(4);
/*
when delete node 4
3
/ \
6 5
/ \ / \
7 9 14 11
*/
obj.deleteNode(14);
/*
when delete node 14
3
/ \
6 5
/ \ / \
7 9 14 11
*/
//when node are not exist
obj.deleteNode(15);
}
main();
Output
1 2 4 7 6 9 11 3 14 5
Delete Node key : 1
2 4 6 7 11 9 3 14 5
Delete Node key : 2
3 4 6 7 9 5 14 11
Delete Node key : 4
3 6 7 9 5 14 11
Delete Node key : 14
3 6 7 9 5 11
Delete key 15 not exist
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