Binary Min Heap Tree Node Deletion

Binary min heap 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







© 2021, kalkicode.com, All rights reserved