Binary Max Heap Tree Node Deletion

Here given code implementation process.

``````/*
C++ program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
#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 MaxHeap {
public:

//This is use to store information of number of nodes in Max heap
int size;
Node *root;
MaxHeap() {
this->root = NULL;
this->size = 0;
}
//Get height of insert new node
int tree_height() {
int i = 1;
int sum = 0;
while (this->size > sum + (1 << i)) {
sum += (1 << i);
i++;
}
return i;
}
//interchange the two node value
void swap_node(Node *first, Node *second) {
int temp = first->key;
first->key = second->key;
second->key = temp;
}
//Arrange node key
}
}
}
if (level >= height) {
return false;
}
if (level - 1 == height &&
} else {
}
return true;
}
//Check effect of new inserted node
return true;
}
}
return false;
}
//Handles the request to new inserting node
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->arrange_node(this->root);
} else
if (this->root->right == NULL) {
this->root->right = new Node(value);
this->arrange_node(this->root);
} else {
int height = this->tree_height();
}
this->size++;
}
cout << " " << head->key;
}
}
Node *node_parent(Node *head, int value) {
}
if (element == NULL) {
}
return element;
}
}
//Find last node of tree
Node *tree_last_node(Node *head, int height, int level) {
if (level == height - 1 &&
}
Node *element = this->tree_last_node(head->right, height, level + 1);
if (element == NULL) {
element = this->tree_last_node(head->left, height, level + 1);
}
return element;
}
}
return false;
}
return true;
}
void updateDeletion(Node *find_node) {
//Find the new changes to make new max heap
//O(long h)
while (find_node != NULL) {
//Check max heap properties

if (this->is_max_heap(find_node) == false) {
//fail max heap

if (find_node->left != NULL &&
find_node->right != NULL) {
//Repace data with maximum value

if (find_node->left->key > find_node->right->key) {
this->swap_node(find_node, find_node->left);
find_node = find_node->left;
} else {
this->swap_node(find_node, find_node->right);
find_node = find_node->right;
}
} else
if (find_node->right != NULL) {
this->swap_node(find_node, find_node->right);
find_node = find_node->right;
} else {
this->swap_node(find_node, find_node->left);
find_node = find_node->left;
}
} else {
break;
}
}
}
void delete_node(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) {
//Delete root node
this->root = NULL;
} else
if (this->root->key == value &&
this->root->right == NULL) {
//Only two node in max heap
find_node = this->root;
this->root = this->root->left;
find_node = NULL;
} else {
//Find the max height by using tree node size
int height = this->tree_height();
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 = this->tree_last_node(this->root, height, 0);
if (last_root != NULL) {
//updtae key value

if (last_root->right != NULL) {
this->root->key = last_root->right->key;
//remove last node
last_root->right = NULL;
} else {
this->root->key = last_root->left->key;
//remove last node
last_root->left = NULL;
}
this->updateDeletion(this->root);
}
}
cout << "\nDelete Node key : " << value << "\n";
this->preorder(this->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 = this->node_parent(this->root, value);
if (find_node == NULL) {
cout << "\nDelete key " << value << " not exist ";
} else {
//Find the max height by using tree node size
int height = this->tree_height();
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 = this->tree_last_node(this->root, height, 0);
if (last_root != NULL) {
if (last_root == find_node) {
//When delete last 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->swap_node(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 {
find_node->key = last_root->left->key;
//remove last node
last_root->left = NULL;
}
}
this->updateDeletion(find_node);
cout << "\nDelete Node key : " << value << "\n";
this->preorder(this->root);
//modify tree node size
this->size--;
}
}
}
} else {
cout << "Empty max heap\n";
}
}
};
int main() {
MaxHeap obj =  MaxHeap();
//Construct first max 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*/
/*
14
/     \
11      9
/  \    /  \
6    7  4    2
/ \   /
1   3 5
*/
//preorder 14  11  6  1  3  7  5  9  4  2
obj.preorder(obj.root);
obj.delete_node(1);
/*
when delete node 1

14
/     \
11      9
/  \    /  \
6    7  4    2
/ \
5   3
*/
obj.delete_node(2);
/*
when delete node 2

14
/     \
11      9
/  \    /  \
6    7  4    3
/
5
*/
obj.delete_node(4);
/*
when delete node 4

14
/     \
11      9
/  \    /  \
6    7  5    3

*/
obj.delete_node(14);
/*
when delete node 14

First make last node as root
3
/     \
11      9
/  \    /
6    7  5

//update node value

11
/     \
7       9
/  \    /
6    3  5

*/
//when node are not exist
obj.delete_node(15);
return 0;
}```
```

Output

`````` 14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist``````
``````/*
Java program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
class Node
{

public Node left;
public Node right;
public int key;

public Node(int value)
{
key = value;
left = null;
right = null;
}
}
public class MaxHeap {

//This is use to store information of number of nodes in Max heap
public int size;

public Node root;

public MaxHeap() {

root = null;

size = 0;
}

//Get height of insert new node
public int tree_height() {
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 swap_node(Node first, Node second) {
int temp = first.key;

first.key = second.key;
second.key = temp;
}
//Arrange node key

}
}
}
if (level >= height) {
return false;
}

if (level - 1 == height && head.left == null || head.right == null) {
} else {
}

return true;
}

//Check effect of new inserted node

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);
arrange_node(root);

} else if (root.right == null) {
root.right = new Node(value);
arrange_node(root);
} else {
int height = tree_height();

}
this.size++;
}

}
}
public Node node_parent(Node head, int value) {

}

if (element == null) {
}

return element;
}
}
//Find last node of tree
public Node tree_last_node(Node head, int height, int level) {

if (level == height - 1 && (head.left != null || head.right != null)) {
}

Node element = tree_last_node(head.right, height, level + 1);

if (element == null) {
element = tree_last_node(head.left, height, level + 1);
}

return element;

}
}

return false;
}
return true;
}
public void updateDeletion(Node find_node) {
//Find the new changes to make new max heap
//O(long h)
while (find_node != null) {
//Check max heap properties
if (is_max_heap(find_node) == false) {
//fail max heap

if (find_node.left != null && find_node.right != null) {
//Repace data with maximum value
if (find_node.left.key > find_node.right.key) {
swap_node(find_node, find_node.left);
find_node = find_node.left;
} else {
swap_node(find_node, find_node.right);
find_node = find_node.right;
}
} else if (find_node.right != null) {
swap_node(find_node, find_node.right);
find_node = find_node.right;
} else {
swap_node(find_node, find_node.left);
find_node = find_node.left;
}

}
else
{
break;
}
}
}

public void delete_node(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 max heap
find_node = root;
root = root.left;
find_node = null;
}
else
{
//Find the max height by using tree node size
int height = tree_height();

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 = tree_last_node(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
{
root.key = last_root.left.key;
//remove last node
last_root.left = null;
}
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 = node_parent(root, value);

if (find_node == null)
{
//In case delete node not exist
System.out.print("\nDelete key " + value + " not exist ");
}
else
{

//Find the max height by using tree node size
int height = tree_height();

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 = tree_last_node(root, height, 0);

if (last_root != null)
{

if (last_root == find_node)
{
//When delete last 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)
{

swap_node(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
{
find_node.key = last_root.left.key;
//remove last node
last_root.left = null;
}

}
updateDeletion(find_node);
System.out.print("\nDelete Node key : " + value + "\n");
preorder(root);
//modify tree node size
this.size--;
}
}
}
} else {
System.out.print("Empty max heap\n");
}

}

public static void main(String[] args) {

MaxHeap obj = new MaxHeap();

//Construct first max 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*/

/*
14
/     \
11      9
/  \    /  \
6    7  4    2
/ \   /
1   3 5
*/
//preorder 14  11  6  1  3  7  5  9  4  2

obj.preorder(obj.root);
obj.delete_node(1);
/*
when delete node 1

14
/     \
11      9
/  \    /  \
6    7  4    2
/ \
5   3
*/

obj.delete_node(2);
/*
when delete node 2

14
/     \
11      9
/  \    /  \
6    7  4    3
/
5
*/
obj.delete_node(4);

/*
when delete node 4

14
/     \
11      9
/  \    /  \
6    7  5    3

*/

obj.delete_node(14);

/*
when delete node 14

First make last node as root
3
/     \
11      9
/  \    /
6    7  5

//update node value

11
/     \
7       9
/  \    /
6    3  5

*/
//when node are not exist
obj.delete_node(15);
}
}```
```

Output

`````` 14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist``````
``````/*
C# program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
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 MaxHeap {
//This is use to store information of number of nodes in Max heap
public int size;
public Node root;
public MaxHeap() {
root = null;
size = 0;
}
//Get height of insert new node
public int tree_height() {
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 swap_node(Node first, Node second) {
int temp = first.key;
first.key = second.key;
second.key = temp;
}
//Arrange node key
}
}
}
if (level >= height) {
return false;
}
if (level - 1 == height &&
} else {
}
return true;
}
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);
arrange_node(root);
} else
if (root.right == null) {
root.right = new Node(value);
arrange_node(root);
} else {
int height = tree_height();
}
this.size++;
}
}
}
public Node node_parent(Node head, int value) {
}
if (element == null) {
}
return element;
}
}
//Find last node of tree
public Node tree_last_node(Node head, int height, int level) {
if (level == height - 1 &&
}
Node element = tree_last_node(head.right, height, level + 1);
if (element == null) {
element = tree_last_node(head.left, height, level + 1);
}
return element;
}
}
return false;
}
return true;
}
public void updateDeletion(Node find_node) {
//Find the new changes to make new max heap
//O(long h)
while (find_node != null) {
//Check max heap properties

if (is_max_heap(find_node) == false) {
//fail max heap

if (find_node.left != null &&
find_node.right != null) {
//Repace data with maximum value

if (find_node.left.key > find_node.right.key) {
swap_node(find_node, find_node.left);
find_node = find_node.left;
} else {
swap_node(find_node, find_node.right);
find_node = find_node.right;
}
} else
if (find_node.right != null) {
swap_node(find_node, find_node.right);
find_node = find_node.right;
} else {
swap_node(find_node, find_node.left);
find_node = find_node.left;
}
} else {
break;;
}
}
}
public void delete_node(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 max heap
find_node = root;
root = root.left;
find_node = null;
} else {
//Find the max height by using tree node size
int height = tree_height();
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 = tree_last_node(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 {
root.key = last_root.left.key;
//remove last node
last_root.left = null;
}
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 = node_parent(root, value);
if (find_node == null) {
Console.Write("\nDelete key " + value + " not exist ");
} else {
//Find the max height by using tree node size
int height = tree_height();
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 = tree_last_node(root, height, 0);
if (last_root != null) {
if (last_root == find_node) {
//When delete last 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) {
swap_node(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 {
find_node.key = last_root.left.key;
//remove last node
last_root.left = null;
}
}
updateDeletion(find_node);
Console.Write("\nDelete Node key : " + value + "\n");
preorder(root);
//modify tree node size
this.size--;
}
}
}
} else {
Console.Write("Empty max heap\n");
}
}
public static void Main(String[] args) {
MaxHeap obj = new MaxHeap();
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);
obj.preorder(obj.root);
obj.delete_node(1);
obj.delete_node(2);
obj.delete_node(4);
obj.delete_node(14);
obj.delete_node(15);
}
}```
```

Output

`````` 14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist``````
``````<?php
/*
Php program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
class Node {
public \$left;
public \$right;
public \$key;

function __construct(\$value) {
\$this->key = \$value;
\$this->left = null;
\$this->right = null;
}
}
class MaxHeap {
//This is use to store information of number of nodes in Max heap
public \$size;
public \$root;

function __construct() {
\$this->root = null;
\$this->size = 0;
}
//Get height of insert new node

public  function tree_height() {
\$i = 1;
\$sum = 0;
while (\$this->size > \$sum + (1 << \$i)) {
\$sum += (1 << \$i);
\$i++;
}
return \$i;
}
//interchange the two node value

public  function swap_node(\$first, \$second) {
\$temp = \$first->key;
\$first->key = \$second->key;
\$second->key = \$temp;
}
//Arrange node key

}
}
}
if (\$level >= \$height) {
return false;
}
if (\$level - 1 == \$height &&
} else {
}
return true;
}
//Check effect of new inserted node
return true;
}
}
return false;
}
//Handles the request to new inserting node

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->arrange_node(\$this->root);
} else
if (\$this->root->right == null) {
\$this->root->right = new Node(\$value);
\$this->arrange_node(\$this->root);
} else {
\$height = \$this->tree_height();
}
\$this->size++;
}
}
}
}
if (\$element == null) {
}
return \$element;
}
}
//Find last node of tree

public  function tree_last_node(\$head, \$height, \$level) {
if (\$level == \$height - 1 &&
}
\$element = \$this->tree_last_node(\$head->right, \$height, \$level + 1);
if (\$element == null) {
\$element = \$this->tree_last_node(\$head->left, \$height, \$level + 1);
}
return \$element;
}
}
return false;
}
return true;
}
public  function updateDeletion(\$find_node) {
//Find the new changes to make new max heap
//O(long h)
while (\$find_node != null) {
//Check max heap properties

if (\$this->is_max_heap(\$find_node) == false) {
//fail max heap

if (\$find_node->left != null &&
\$find_node->right != null) {
//Repace data with maximum value

if (\$find_node->left->key > \$find_node->right->key) {
\$this->swap_node(\$find_node, \$find_node->left);
\$find_node = \$find_node->left;
} else {
\$this->swap_node(\$find_node, \$find_node->right);
\$find_node = \$find_node->right;
}
} else
if (\$find_node->right != null) {
\$this->swap_node(\$find_node, \$find_node->right);
\$find_node = \$find_node->right;
} else {
\$this->swap_node(\$find_node, \$find_node->left);
\$find_node = \$find_node->left;
}
} else {
break;
}
}
}
public  function delete_node(\$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) {
//Delete root node
\$this->root = null;
} else
if (\$this->root->key == \$value &&
\$this->root->right == null) {
//Only two node in max heap
\$find_node = \$this->root;
\$this->root = \$this->root->left;
\$find_node = null;
} else {
//Find the max height by using tree node size
\$height = \$this->tree_height();
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 = \$this->tree_last_node(\$this->root, \$height, 0);
if (\$last_root != null) {
//updtae key value

if (\$last_root->right != null) {
\$this->root->key = \$last_root->right->key;
//remove last node
\$last_root->right = null;
} else {
\$this->root->key = \$last_root->left->key;
//remove last node
\$last_root->left = null;
}
\$this->updateDeletion(\$this->root);
}
}
echo("\nDelete Node key : ". \$value ."\n");
\$this->preorder(\$this->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 = \$this->node_parent(\$this->root, \$value);
if (\$find_node == null) {
//In case delete node not exist

echo("\nDelete key ". \$value ." not exist ");
} else {
//Find the max height by using tree node size
\$height = \$this->tree_height();
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 = \$this->tree_last_node(\$this->root, \$height, 0);
if (\$last_root != null) {
if (\$last_root == \$find_node) {
//When delete last 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->swap_node(\$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 {
\$find_node->key = \$last_root->left->key;
//remove last node
\$last_root->left = null;
}
}
\$this->updateDeletion(\$find_node);
echo("\nDelete Node key : ". \$value ."\n");
\$this->preorder(\$this->root);
//modify tree node size
\$this->size--;
}
}
}
} else {
echo("Empty max heap\n");
}
}
}

function main() {
\$obj = new MaxHeap();
//Construct first max 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*/
/*
14
/     \
11      9
/  \    /  \
6    7  4    2
/ \   /
1   3 5
*/
//preorder 14  11  6  1  3  7  5  9  4  2
\$obj->preorder(\$obj->root);
\$obj->delete_node(1);
/*
when delete node 1

14
/     \
11      9
/  \    /  \
6    7  4    2
/ \
5   3
*/
\$obj->delete_node(2);
/*
when delete node 2

14
/     \
11      9
/  \    /  \
6    7  4    3
/
5
*/
\$obj->delete_node(4);
/*
when delete node 4

14
/     \
11      9
/  \    /  \
6    7  5    3

*/
\$obj->delete_node(14);
/*
when delete node 14

First make last node as root
3
/     \
11      9
/  \    /
6    7  5

//update node value

11
/     \
7       9
/  \    /
6    3  5

*/
//when node are not exist
\$obj->delete_node(15);

}
main();```
```

Output

`````` 14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist``````
``````/*
Node Js program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
class Node {
constructor(value) {
this.key = value;
this.left = null;
this.right = null;
}
}
class MaxHeap {
//This is use to store information of number of nodes in Max heap

constructor() {
this.root = null;
this.size = 0;
}

//Get height of insert new node
tree_height() {
var i = 1;
var sum = 0;
while (this.size > sum + (1 << i)) {
sum += (1 << i);
i++;
}

return i;
}

//interchange the two node value
swap_node(first, second) {
var temp = first.key;
first.key = second.key;
second.key = temp;
}

//Arrange node key
}

}
}
if (level >= height) {
return false;
}

if (level - 1 == height &&
} else {
}
return true;
}

//Check effect of new inserted node
return true;
}
}

return false;
}

//Handles the request to new inserting node
insert(value) {
if (this.root == null) {
this.root = new Node(value);
} else
if (this.root.left == null) {
this.root.left = new Node(value);
this.arrange_node(this.root);
} else
if (this.root.right == null) {
this.root.right = new Node(value);
this.arrange_node(this.root);
} else {
var height = this.tree_height();
}
this.size++;
}
}
}
}
if (element == null) {
}

return element;
}

}

//Find last node of tree
if (level == height - 1 &&
}
var element = this.tree_last_node(head.right, height, level + 1);
if (element == null) {
element = this.tree_last_node(head.left, height, level + 1);
}

return element;
}

}
return false;
}

return true;
}
updateDeletion(find_node) {
//Find the new changes to make new max heap
//O(long h)
while (find_node != null) {
//Check max heap properties

if (this.is_max_heap(find_node) == false) {
//fail max heap

if (find_node.left != null &&
find_node.right != null) {
//Repace data with maximum value

if (find_node.left.key > find_node.right.key) {
this.swap_node(find_node, find_node.left);
find_node = find_node.left;
} else {
this.swap_node(find_node, find_node.right);
find_node = find_node.right;
}
} else
if (find_node.right != null) {
this.swap_node(find_node, find_node.right);
find_node = find_node.right;
} else {
this.swap_node(find_node, find_node.left);
find_node = find_node.left;
}
} else {
break;
}
}
}
delete_node(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) {
//Delete root node
this.root = null;
} else
if (this.root.key == value &&
this.root.right == null) {
//Only two node in max heap
find_node = this.root;
this.root = this.root.left;
find_node = null;
} else {
//Find the max height by using tree node size
var height = this.tree_height();
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 = this.tree_last_node(this.root, height, 0);
if (last_root != null) {
//updtae key value

if (last_root.right != null) {
this.root.key = last_root.right.key;
//remove last node
last_root.right = null;
} else {
this.root.key = last_root.left.key;
//remove last node
last_root.left = null;
}
this.updateDeletion(this.root);
}
}

process.stdout.write("\nDelete Node key : " + value + "\n");
this.preorder(this.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 = this.node_parent(this.root, value);
if (find_node == null) {
//In case delete node not exist

process.stdout.write("\nDelete key " + value + " not exist ");
} else {
//Find the max height by using tree node size
var height = this.tree_height();
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 = this.tree_last_node(this.root, height, 0);
if (last_root != null) {
if (last_root == find_node) {
//When delete last 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.swap_node(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 {
find_node.key = last_root.left.key;
//remove last node
last_root.left = null;
}
}
this.updateDeletion(find_node);
process.stdout.write("\nDelete Node key : " + value + "\n");
this.preorder(this.root);
//modify tree node size
this.size--;
}
}
}
} else {
process.stdout.write("Empty max heap\n");
}
}
}

function main(args) {
var obj = new MaxHeap();
//Construct first max 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*/
/*
14
/     \
11      9
/  \    /  \
6    7  4    2
/ \   /
1   3 5
*/
//preorder 14  11  6  1  3  7  5  9  4  2
obj.preorder(obj.root);
obj.delete_node(1);
/*
when delete node 1

14
/     \
11      9
/  \    /  \
6    7  4    2
/ \
5   3
*/
obj.delete_node(2);
/*
when delete node 2

14
/     \
11      9
/  \    /  \
6    7  4    3
/
5
*/
obj.delete_node(4);
/*
when delete node 4

14
/     \
11      9
/  \    /  \
6    7  5    3

*/
obj.delete_node(14);
/*
when delete node 14

First make last node as root
3
/     \
11      9
/  \    /
6    7  5

//update node value

11
/     \
7       9
/  \    /
6    3  5

*/
//when node are not exist
obj.delete_node(15);
}

main();```
```

Output

`````` 14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist``````
``````#   Python 3 program
#   Binary Max Heap Tree Node Deletion

# Binary max heap node
class Node :

def __init__(self, value) :
self.key = value
self.left = None
self.right = None

class MaxHeap :
# This is use to store information of number of nodes in Max heap
def __init__(self) :
self.root = None
self.size = 0

# Get height of insert new node
def tree_height(self) :
i = 1
sum = 0
while (self.size > sum + (1 << i)) :
sum += (1 << i)
i += 1

return i

# interchange the two node value
def swap_node(self, first, second) :
temp = first.key
first.key = second.key
second.key = temp

# Arrange node key

if (level >= height) :
return False

if (level - 1 == height and head.left == None or head.right == None) :
else :

return True

# Check effect of new inserted node
return True

return False

# Handles the request to new inserting node
def insert(self, value) :
if (self.root == None) :
self.root = Node(value)
elif (self.root.left == None) :
self.root.left = Node(value)
self.arrange_node(self.root)
elif (self.root.right == None) :
self.root.right = Node(value)
self.arrange_node(self.root)
else :
height = self.tree_height()

self.size += 1

print(" ", head.key, end = "")

if (element == None) :

return element

# Find last node of tree
def tree_last_node(self, head, height, level) :
if (level == height - 1 and(head.left != None or head.right != None)) :

element = self.tree_last_node(head.right, height, level + 1)
if (element == None) :
element = self.tree_last_node(head.left, height, level + 1)

return element

return False

return True

def updateDeletion(self, find_node) :
# Find the new changes to make new max heap
# O(long h)
while (find_node != None) :
# Check max heap properties

if (self.is_max_heap(find_node) == False) :
# fail max heap

if (find_node.left != None and find_node.right != None) :
# Repace data with maximum value

if (find_node.left.key > find_node.right.key) :
self.swap_node(find_node, find_node.left)
find_node = find_node.left
else :
self.swap_node(find_node, find_node.right)
find_node = find_node.right

elif (find_node.right != None) :
self.swap_node(find_node, find_node.right)
find_node = find_node.right
else :
self.swap_node(find_node, find_node.left)
find_node = find_node.left

else :
break

def delete_node(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) :
# Delete root node
self.root = None
elif (self.root.key == value and self.root.right == None) :
# Only two node in max heap
find_node = self.root
self.root = self.root.left
find_node = None
else :
# Find the max height by using tree node size
height = self.tree_height()
if ((1 << height) - 1 == self.size) :
# in case given height is a perfect of all leaf
height -= 1

# Find parent of a last node of tree
last_root = self.tree_last_node(self.root, height, 0)
if (last_root != None) :
# updtae key value

if (last_root.right != None) :
self.root.key = last_root.right.key
# remove last node
last_root.right = None
else :
self.root.key = last_root.left.key
# remove last node
last_root.left = None

self.updateDeletion(self.root)

print("\nDelete Node key : ", value ,"\n", end = "")
self.preorder(self.root)
# modify tree node size
self.size -= 1
else :
# When root node is not a part of delete node
# Find parent of a delete node key
find_node = self.node_parent(self.root, value)
if (find_node == None) :
# In case delete node not exist
print("\nDelete key ", value ," not exist ", end = "")
else :
# Find the max height by using tree node size
height = self.tree_height()
if ((1 << height) - 1 == self.size) :
# In case given height is a same of all leaf
height -= 1

# Find parent of a last node of tree
last_root = self.tree_last_node(self.root, height, 0)
if (last_root != None) :
if (last_root == find_node) :
# When delete last 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.swap_node(last_root.right, last_root.left)
last_root.right = None
else :
last_root.left = None

else :
# Get actual delete node location

if (find_node.right != None and find_node.right.key == value) :
find_node = find_node.right
else :
find_node = find_node.left

# Updtae key value

if (last_root.right != None) :
find_node.key = last_root.right.key
# remove last node
last_root.right = None
else :
find_node.key = last_root.left.key
# remove last node
last_root.left = None

self.updateDeletion(find_node)
print("\nDelete Node key : ", value ,"\n", end = "")
self.preorder(self.root)
# modify tree node size
self.size -= 1

else :
print("Empty max heap\n", end = "")

def main() :
obj = MaxHeap()
# Construct first max 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)
# preorder 14  11  6  1  3  7  5  9  4  2
#
#             14
#          /     \
#         11      9
#        /  \    /  \
#       6    7  4    2
#      / \   /
#     1   3 5
#

# After insert element

obj.preorder(obj.root)
obj.delete_node(1)
#
#       when delete node 1
#             14
#          /     \
#         11      9
#        /  \    /  \
#       6    7  4    2
#      / \
#     5   3
#

obj.delete_node(2)
#
#       when delete node 2
#             14
#          /     \
#         11      9
#        /  \    /  \
#       6    7  4    3
#      /
#     5
#

obj.delete_node(4)
#
#       when delete node 4
#             14
#          /     \
#         11      9
#        /  \    /  \
#       6    7  5    3
#
#
#

obj.delete_node(14)
# when node are not exist
#
#       when delete node 14
#       First make last node as root
#             3
#          /     \
#         11      9
#        /  \    /
#       6    7  5
#
#       //update node value
#
#             11
#          /     \
#         7       9
#        /  \    /
#       6    3  5
#
#
#

obj.delete_node(15)

if __name__ == "__main__":
main()```
```

Output

``````  14  11  6  1  3  7  5  9  4  2
Delete Node key :  1
14  11  6  5  3  7  9  4  2
Delete Node key :  2
14  11  6  5  7  9  4  3
Delete Node key :  4
14  11  6  7  9  5  3
Delete Node key :  14
11  7  6  3  9  5
Delete key  15  not exist``````
``````#   Ruby program
#   Binary Max Heap Tree Node Deletion

# Binary max heap node
class Node
# Define the accessor and reader of class Node
attr_accessor :left, :right, :key

def initialize(value)
@key = value
@left = nil
@right = nil
end
end
class MaxHeap
# Define the accessor and reader of class MaxHeap
attr_accessor :size, :root
# This is use to store information of number of nodes in Max heap
def initialize()
@root = nil
@size = 0
end
# Get height of insert new node
def tree_height()
i = 1
sum = 0
while (self.size > sum + (1 << i))
sum += (1 << i)
i += 1
end
return i
end
# interchange the two node value
def swap_node(first, second)
temp = first.key
first.key = second.key
second.key = temp
end
# Arrange node key
end
end
end
if (level >= height)
return false
end
if (level - 1 == height &&
else
end
return true
end
# Check effect of new inserted node
return true
end
end
return false
end
# Handles the request to new inserting node
def insert(value)
if (@root == nil)
@root = Node.new(value)
elsif (@root.left == nil)
@root.left = Node.new(value)
self.arrange_node(@root)
elsif (@root.right == nil)
@root.right = Node.new(value)
self.arrange_node(@root)
else
height = self.tree_height()
end
self.size += 1
end
end
end
end
if (element == nil)
end
return element
end
end
# Find last node of tree
if (level == height - 1 &&
end
element = self.tree_last_node(head.right, height, level + 1)
if (element == nil)
element = self.tree_last_node(head.left, height, level + 1)
end
return element
end
end
return false
end
return true
end
def updateDeletion(find_node)
# Find the new changes to make new max heap
# O(long h)
while (find_node != nil)
# Check max heap properties

if (self.is_max_heap(find_node) == false)
# fail max heap

if (find_node.left != nil &&
find_node.right != nil)
# Repace data with maximum value

if (find_node.left.key > find_node.right.key)
self.swap_node(find_node, find_node.left)
find_node = find_node.left
else
self.swap_node(find_node, find_node.right)
find_node = find_node.right
end
elsif (find_node.right != nil)
self.swap_node(find_node, find_node.right)
find_node = find_node.right
else
self.swap_node(find_node, find_node.left)
find_node = find_node.left
end
else
break
end
end
end
def delete_node(value)
if (@root != nil)
find_node = nil
last_root = nil
if (@root.key == value)
if (@root.left == nil &&
@root.right == nil)
# Delete root node
@root = nil
elsif (@root.key == value &&
@root.right == nil)
# Only two node in max heap
find_node = @root
@root = @root.left
find_node = nil
else
# Find the max height by using tree node size
height = self.tree_height()
if ((1 << height) - 1 == self.size)
# in case given height is a perfect of all leaf
height -= 1
end
# Find parent of a last node of tree
last_root = self.tree_last_node(@root, height, 0)
if (last_root != nil)
# updtae key value

if (last_root.right != nil)
@root.key = last_root.right.key
# remove last node
last_root.right = nil
else
@root.key = last_root.left.key
# remove last node
last_root.left = nil
end
self.updateDeletion(@root)
end
end
print("\nDelete Node key  :", value ,"\n")
self.preorder(@root)
# modify tree node size
self.size -= 1
else
# When root node is not a part of delete node
# Find parent of a delete node key
find_node = self.node_parent(@root, value)
if (find_node == nil)
# In case delete node not exist

print("\nDelete key ", value ," not exist ")
else
# Find the max height by using tree node size
height = self.tree_height()
if ((1 << height) - 1 == self.size)
# In case given height is a same of all leaf
height -= 1
end
# Find parent of a last node of tree
last_root = self.tree_last_node(@root, height, 0)
if (last_root != nil)
if (last_root == find_node)
# When delete last node

if (last_root.right != nil &&
last_root.right.key == value)
last_root.right = nil
elsif (last_root.left != nil &&
last_root.left.key == value)
if (last_root.right != nil)
self.swap_node(last_root.right, last_root.left)
last_root.right = nil
else
last_root.left = nil
end
end
else
# Get actual delete node location

if (find_node.right != nil &&
find_node.right.key == value)
find_node = find_node.right
else
find_node = find_node.left
end
# Updtae key value

if (last_root.right != nil)
find_node.key = last_root.right.key
# remove last node
last_root.right = nil
else
find_node.key = last_root.left.key
# remove last node
last_root.left = nil
end
end
self.updateDeletion(find_node)
print("\nDelete Node key  : ", value ,"\n")
self.preorder(@root)
# modify tree node size
self.size -= 1
end
end
end
else
print("Empty max heap\n")
end
end
end
def main()
obj = MaxHeap.new()
# Construct first max 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)
# preorder 14  11  6  1  3  7  5  9  4  2
#
#             14
#          /     \
#         11      9
#        /  \    /  \
#       6    7  4    2
#      / \   /
#     1   3 5
#

# After insert element

obj.preorder(obj.root)
obj.delete_node(1)
#
#       when delete node 1
#             14
#          /     \
#         11      9
#        /  \    /  \
#       6    7  4    2
#      / \
#     5   3
#

obj.delete_node(2)
#
#       when delete node 2
#             14
#          /     \
#         11      9
#        /  \    /  \
#       6    7  4    3
#      /
#     5
#

obj.delete_node(4)
#
#       when delete node 4
#             14
#          /     \
#         11      9
#        /  \    /  \
#       6    7  5    3
#
#
#

obj.delete_node(14)
# when node are not exist
#
#       when delete node 14
#       First make last node as root
#             3
#          /     \
#         11      9
#        /  \    /
#       6    7  5
#
#       //update node value
#
#             11
#          /     \
#         7       9
#        /  \    /
#       6    3  5
#
#
#

obj.delete_node(15)
end
main()```
```

Output

`````` 14 11 6 1 3 7 5 9 4 2
Delete Node key  : 1
14 11 6 5 3 7 9 4 2
Delete Node key  : 2
14 11 6 5 7 9 4 3
Delete Node key  : 4
14 11 6 7 9 5 3
Delete Node key  :14
11 7 6 3 9 5
Delete key 15 not exist ``````
``````/*
Scala program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
class Node(var left: Node,
var right: Node,
var key: Int) {
def this(value: Int) {
this(null,null,value);
}
}
class MaxHeap(var size: Int,
var root: Node) {
//size is use to store information of number of nodes in Max heap
def this() {
this(0,null);
}
//Get height of insert new node
def tree_height(): Int = {
var i: Int = 1;
var sum: Int = 0;
while (this.size > sum + (1 << i)) {
sum += (1 << i);
i += 1;
}
return i;
}
//interchange the two node value
def swap_node(first: Node, second: Node): Unit = {
var temp: Int = first.key;
first.key = second.key;
second.key = temp;
}
//Arrange node key
def arrange_node(head: Node): Unit = {
}
}
}
def add_node(head: Node, height: Int, level: Int, value: Int): Boolean = {
if (level >= height) {
return false;
}
if (level - 1 == height &&
} else {
}

return true;
}
//Check effect of new inserted node

return true;
}
}
return false;
}
//Handles the request to new inserting node
def insert(value: Int): Unit = {
if (root == null) {
root = new Node(value);
} else
if (root.left == null) {
root.left = new Node(value);
arrange_node(root);
} else
if (root.right == null) {
root.right = new Node(value);
arrange_node(root);
} else {
var height: Int = tree_height();
}
this.size += 1;
}
def preorder(head: Node): Unit = {
}
}
def node_parent(head: Node, value: Int): Node = {
}
var element: Node = node_parent(head.left, value);

if (element == null) {
}
return element;
}
}
//Find last node of tree
def tree_last_node(head: Node, height: Int, level: Int): Node = {
if (level == height - 1 &&
}
var element: Node = tree_last_node(head.right, height, level + 1);

if (element == null) {
element = tree_last_node(head.left, height, level + 1);
}
return element;
}
}
def is_max_heap(head: Node): Boolean = {
return false;
}
return true;
}
def updateDeletion(element: Node): Unit = {
//Find the new changes to make new max heap
//O(long h)
var find_node: Node = element;
while (find_node != null) {
//Check max heap properties

if (is_max_heap(find_node) == false) {
//fail max heap

if (find_node.left != null &&
find_node.right != null) {
//Repace data with maximum value

if (find_node.left.key > find_node.right.key) {
swap_node(find_node, find_node.left);
find_node = find_node.left;
} else {
swap_node(find_node, find_node.right);
find_node = find_node.right;
}
} else
if (find_node.right != null) {
swap_node(find_node, find_node.right);
find_node = find_node.right;
} else {
swap_node(find_node, find_node.left);
find_node = find_node.left;
}
} else {
return;
}
}
}
def delete_node(value: Int): Unit = {
if (root != null) {
var find_node: Node = null;
var last_root: Node = null;
var height: Int = 0;
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 max heap
find_node = root;
root = root.left;
find_node = null;
} else {
//Find the max height by using tree node size
height = tree_height();

if ((1 << height) - 1 == this.size) {
//in case given height is a perfect of all leaf
height -= 1;
}
//Find parent of a last node of tree
last_root = tree_last_node(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 {
root.key = last_root.left.key;

//remove last node
last_root.left = null;
}
updateDeletion(root);
}
}
print("\nDelete Node key : " + value + "\n");
preorder(root);

//modify tree node size
this.size -= 1;
} else {
//When root node is not a part of delete node
//Find parent of a delete node key
find_node = node_parent(root, value);

if (find_node == null) {
//In case delete node not exist
print("\nDelete key " + value + " not exist ");
} else {
//Find the max height by using tree node size
height = this.tree_height();

if ((1 << height) - 1 == this.size) {
//In case given height is a same of all leaf
height -= 1;
}
//Find parent of a last node of tree
last_root = tree_last_node(root, height, 0);

if (last_root != null) {
if (last_root == find_node) {
//When delete last 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) {
swap_node(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 {
find_node.key = last_root.left.key;

//remove last node
last_root.left = null;
}
}
updateDeletion(find_node);
print("\nDelete Node key : " + value + "\n");
preorder(root);

//modify tree node size
this.size -= 1;
}
}
}
} else {
print("Empty max heap\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MaxHeap = new MaxHeap();

//Construct first max 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*/
/*
14
/     \
11      9
/  \    /  \
6    7  4    2
/ \   /
1   3 5
*/
//preorder 14  11  6  1  3  7  5  9  4  2
obj.preorder(obj.root);
obj.delete_node(1);

/*
when delete node 1

14
/     \
11      9
/  \    /  \
6    7  4    2
/ \
5   3
*/
obj.delete_node(2);

/*
when delete node 2

14
/     \
11      9
/  \    /  \
6    7  4    3
/
5
*/
obj.delete_node(4);

/*
when delete node 4

14
/     \
11      9
/  \    /  \
6    7  5    3

*/
obj.delete_node(14);

/*
when delete node 14

First make last node as root
3
/     \
11      9
/  \    /
6    7  5

//update node value

11
/     \
7       9
/  \    /
6    3  5

*/
//when node are not exist
obj.delete_node(15);
}
}```
```

Output

`````` 14 11 6 1 3 7 5 9 4 2
Delete Node key : 1
14 11 6 5 3 7 9 4 2
Delete Node key : 2
14 11 6 5 7 9 4 3
Delete Node key : 4
14 11 6 7 9 5 3
Delete Node key : 14
11 7 6 3 9 5
Delete key 15 not exist``````
``````/*
Swift program
Binary Max Heap Tree Node Deletion
*/
//Binary max heap node
class Node {
var left: Node? ;
var right: Node? ;
var key: Int;
init(_ value: Int) {
self.key = value;
self.left = nil;
self.right = nil;
}
}
class MaxHeap {
//This is use to store information of number of nodes in Max heap
var size: Int;
var root: Node? ;
init() {
self.root = nil;
self.size = 0;
}
//Get height of insert new node
func tree_height() -> Int {
var i: Int = 1;
var sum: Int = 0;
while (self.size > sum + (1 << i)) {
sum += (1 << i);
i += 1;
}
return i;
}
//interchange the two node value
func swap_node(_ first: Node? , _ second : Node? ) {
let temp: Int = first!.key;
first!.key = second!.key;
second!.key = temp;
}
//Arrange node key
func arrange_node(_ head: Node? ) {
}
}
}
func add_node(_ head: Node? , _ height : Int, _ level: Int, _ value: Int) -> Bool {
if (level >= height) {
return false;
}
if (level - 1 == height &&
} else {
}
return true;
}
//Check effect of new inserted node
return true;
}
}
return false;
}
//Handles the request to new inserting node
func insert(_ value: Int) {
if (self.root == nil) {
self.root = Node(value);
} else
if (self.root!.left == nil) {
self.root!.left = Node(value);
self.arrange_node(self.root);
} else
if (self.root!.right == nil) {
self.root!.right = Node(value);
self.arrange_node(self.root);
} else {
let height: Int = self.tree_height();
let _ = self.add_node(self.root, height, 0, value);
}
self.size += 1;
}
func preorder(_ head: Node? ) {
}
}
func node_parent(_ head: Node? , _ value : Int) -> Node? {
}
var element: Node? = self.node_parent(head!.left, value);
if (element == nil) {
}
return element;
}
}
//Find last node of tree
func tree_last_node(_ head: Node? , _ height : Int, _ level: Int) -> Node? {
if (level == height - 1 &&
}
var element: Node? = self.tree_last_node(head!.right, height, level + 1);
if (element == nil) {
element = self.tree_last_node(head!.left, height, level + 1);
}
return element;
}
}
func is_max_heap(_ head: Node? ) -> Bool {
return false;
}
return true;
}
func updateDeletion(_ element: Node? ) {
var find_node : Node? = element;
//Find the new changes to make new max heap
//O(long h)
while (find_node != nil) {
//Check max heap properties

if (self.is_max_heap(find_node) == false) {
//fail max heap

if (find_node!.left != nil &&
find_node!.right != nil) {
//Repace data with maximum value

if (find_node!.left!.key > find_node!.right!.key) {
self.swap_node(find_node, find_node!.left);
find_node = find_node!.left;
} else {
self.swap_node(find_node, find_node!.right);
find_node = find_node!.right;
}
} else
if (find_node!.right != nil) {
self.swap_node(find_node, find_node!.right);
find_node = find_node!.right;
} else {
self.swap_node(find_node, find_node!.left);
find_node = find_node!.left;
}
} else {
break;
}
}
}
func delete_node(_ value: Int) {
if (self.root != nil) {
var height: Int = 0;
var find_node: Node? = nil;
var last_root: Node? = nil;
if (self.root!.key == value) {
if (self.root!.left == nil &&
self.root!.right == nil) {
//Delete root node
self.root = nil;
} else
if (self.root!.key == value &&
self.root!.right == nil) {
//Only two node in max heap
find_node = self.root;
self.root = self.root!.left;
find_node = nil;
} else {
//Find the max height by using tree node size
height = self.tree_height();
if ((1 << height) - 1 == self.size) {
//in case given height is a perfect of all leaf
height -= 1;
}
//Find parent of a last node of tree
last_root = self.tree_last_node(self.root, height, 0);
if (last_root != nil) {
//updtae key value

if (last_root!.right != nil) {
self.root!.key = last_root!.right!.key;
//remove last node
last_root!.right = nil;
} else {
self.root!.key = last_root!.left!.key;
//remove last node
last_root!.left = nil;
}
self.updateDeletion(self.root);
}
}
print("\nDelete Node key : ", value ,"\n", terminator: "");
self.preorder(self.root);
//modify tree node size
self.size -= 1;
} else {
//When root node is not a part of delete node
//Find parent of a delete node key
find_node = self.node_parent(self.root, value);
if (find_node == nil) {

//In case delete node not exist
print("\nDelete key ", value ," not exist ", terminator: "");
} else {
//Find the max height by using tree node size
height = self.tree_height();
if ((1 << height) - 1 == self.size) {
//In case given height is a same of all leaf
height -= 1;
}
//Find parent of a last node of tree
last_root = self.tree_last_node(self.root, height, 0);
if (last_root != nil) {
if (last_root === find_node) {
//When delete last 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.swap_node(last_root!.right, last_root!.left);
last_root!.right = nil;
} else {
last_root!.left = nil;
}
}
} else {
//Get actual delete node location

if (find_node!.right != nil &&
find_node!.right!.key == value) {
find_node = find_node!.right;
} else {
find_node = find_node!.left;
}
//Updtae key value

if (last_root!.right != nil) {
find_node!.key = last_root!.right!.key;
//remove last node
last_root!.right = nil;
} else {
find_node!.key = last_root!.left!.key;
//remove last node
last_root!.left = nil;
}
}
self.updateDeletion(find_node);
print("\nDelete Node key : ", value ,"\n", terminator: "");
self.preorder(self.root);
//modify tree node size
self.size -= 1;
}
}
}
} else {
print("Empty max heap\n", terminator: "");
}
}
}
func main() {
let obj: MaxHeap = MaxHeap();
//Construct first max 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*/
/*
14
/     \
11      9
/  \    /  \
6    7  4    2
/ \   /
1   3 5
*/
//preorder 14  11  6  1  3  7  5  9  4  2
obj.preorder(obj.root);
obj.delete_node(1);
/*
when delete node 1

14
/     \
11      9
/  \    /  \
6    7  4    2
/ \
5   3
*/
obj.delete_node(2);
/*
when delete node 2

14
/     \
11      9
/  \    /  \
6    7  4    3
/
5
*/
obj.delete_node(4);
/*
when delete node 4

14
/     \
11      9
/  \    /  \
6    7  5    3

*/
obj.delete_node(14);
/*
when delete node 14

First make last node as root
3
/     \
11      9
/  \    /
6    7  5

//update node value

11
/     \
7       9
/  \    /
6    3  5

*/
//when node are not exist
obj.delete_node(15);
}
main();```
```

Output

``````  14  11  6  1  3  7  5  9  4  2
Delete Node key :  1
14  11  6  5  3  7  9  4  2
Delete Node key :  2
14  11  6  5  7  9  4  3
Delete Node key :  4
14  11  6  7  9  5  3
Delete Node key :  14
11  7  6  3  9  5
Delete key  15  not exist``````

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.