Binary Max Heap Tree Node Insertion

We are easily performed heap operations in array. But array are fixed size in most of programming language cannot change dynamically. In this post we are implement binary heap. This are size are not per define and that is stratified the properties of binary max heap.

1) The value of root node should be greater than or equal to child node.

2) Each leaf node should be exist in same level. And tree will be a complete tree.

Basically we can use in a two way to insert node in a binary max heap. By using a queue and recursion. This post is based on second approach. First see an example.

binary max heap implementation

In this example given sequence is already in maxheap format. That is best case scenario. In other case when given sequence is not a form of max heap. In this situation we can need to change node values. For example.

binary max heap insertion

Before view the solution think about how to implement this max heap using recursion in (O (n)) time. here n is the number of node in tree.

Note that in above both example we can add and remove note at any time. Here given code implementation process.

//C Program 
//Binary Max Heap Tree Node Insertion
#include <stdio.h> 
#include <stdlib.h>
#include <stdbool.h> //for bool
struct Node
{
  int key;
  struct Node*left,*right;
};
struct MaxHeap
{

  struct Node * root;
  int size;

};

struct MaxHeap* newHeap()
{

  struct MaxHeap*auxiliary = (struct MaxHeap*)malloc(sizeof(struct MaxHeap));

  if(auxiliary)
  {
    auxiliary->size=0;
    auxiliary->root=NULL;
  }
  else
  {
    printf("Memory overflow\n");
  }
  return auxiliary;
}
struct Node* newNode(int key)
{

  struct Node*auxiliary = (struct Node*)malloc(sizeof(struct Node));

  if(auxiliary)
  {
    auxiliary->key=key;
    auxiliary->left=auxiliary->right=NULL;
  }
  else
  {
    printf("Memory overflow\n");
  }
  return auxiliary;
}
 //Get height of insert new node
int insertHeight(int size)
{
  int i=1;

  int sum=0;

  while(size > sum+(1<<i) )
  {
    sum += (1<<i);
    i++;
  }
  return i;
}
void  swapNode(struct Node *first,struct Node *second)
{
  int key = first->key;

  first->key = second->key;
  second->key = key;
}
  //Arrange node key
void  arrangeNode(struct Node *root)
{

  if(root->left!=NULL && root->left->key > root->key)
  {
    swapNode(root,root->left);
  }
  if(root->right!=NULL && root->right->key > root->key)
  {
    swapNode(root,root->right);
  }
}
bool addNode(struct Node *root, int height ,int level,int key)
{
  if(level >= height )
  {
    return false;
  }
  if(root != NULL)
  {

    if(level-1 == height && root->left == NULL || root->right == NULL)
    {
      if(root->left==NULL)
      {
        root->left=newNode(key);
      }
      else
      {
        root->right=newNode(key);
      }

      arrangeNode(root);

      return true;
    }

    if(addNode(root->left, height, level+1,key) || addNode(root->right, height,level+1,key))
    {
          //Check effect of new inserted node
      arrangeNode(root);

      return true;
    }


  }
  return false;
}
void  insert(struct MaxHeap*heap,int key)
{
  
  //Test case
  if(heap->root==NULL)
  {
    heap->root=newNode(key);
  }
  else if(heap->root->left==NULL)
  {
    heap->root->left = newNode(key);
    arrangeNode( heap->root);

  }
  else if(heap->root->right==NULL)
  {
    heap->root->right = newNode(key);
    arrangeNode( heap->root);
  }
  else
  {
    int height = insertHeight(heap->size);

    addNode(heap->root,height, 0,key);
  }
  heap->size++;
}
void  preorder(struct Node *root)
{
  if(root!=NULL)
  {
    printf("  %d",root->key);
    preorder(root->left);

    preorder(root->right);
  }
}
int main()
{
  struct MaxHeap *heap1=newHeap();

    //Construct first Max heap tree
  insert(heap1,5);
  insert(heap1,7);
  insert(heap1,4);
  insert(heap1,3);
  insert(heap1,9);
  insert(heap1,14);
  insert(heap1,2);
  insert(heap1,1);
  insert(heap1,6);
  insert(heap1,11);



  preorder(heap1->root);
    /*After insert element*/

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

    */



  struct MaxHeap *heap2=newHeap();

  //Construct second Min heap tree
  for (int i=15;i> 0;i-- ) 
  {
    insert(heap2,i);

  }

    /*After insert element*/

    /*
               15
           /       \
          /         \
         14          13
       /   \        /   \
      12    11     10    9
     / \    / \   / \    / \
    8   7  6   5 4   3  2   1
    */
  printf("\n");

  preorder(heap2->root);
  return 0;
}

Output

  14  11  6  1  3  7  5  9  4  2
  15  14  12  8  7  11  6  5  13  10  4  3  9  2  1
//C++ Program 
//Binary Max Heap Tree Node Insertion
#include <iostream>
using namespace std;
class Node
{

public:  
  int key;
  Node*left,*right;
  Node(int key)
  {
    this->key=key;
    left=right=NULL;
  }
};
class MaxHeap
{

public:

  Node * root;
  int size;
  MaxHeap()
  {
    root = NULL;
    size = 0;
  }
  void preorder(Node *root);
  bool addNode(Node *root, int height ,int level,int key);
  void arrangeNode(Node *root);
  int insertHeight();
  void swapNode(Node *first,Node *second);
  void insert(int key);

};
 //Get height of insert new node
int MaxHeap:: insertHeight()
{
  int i=1;

  int sum=0;

  while(this->size > sum+(1<<i) )
  {
    sum += (1<<i);
    i++;
  }
  return i;
}
void MaxHeap:: swapNode(Node *first,Node *second)
{
  int key = first->key;

  first->key = second->key;
  second->key = key;
}
  //Arrange node key
void MaxHeap:: arrangeNode(Node *root)
{

  if(root->left!=NULL && root->left->key > root->key)
  {
    swapNode(root,root->left);
  }
  if(root->right!=NULL && root->right->key > root->key)
  {
    swapNode(root,root->right);
  }
}
bool MaxHeap::  addNode(Node *root, int height ,int level,int key)
{
  if(level >= height )
  {
    return false;
  }
  if(root != NULL)
  {

    if(level-1 == height && root->left == NULL || root->right == NULL)
    {
      if(root->left==NULL)
      {
        root->left=new Node(key);
      }
      else
      {
        root->right=new Node(key);
      }

      arrangeNode(root);

      return true;
    }

    if(addNode(root->left, height, level+1,key) || addNode(root->right, height,level+1,key))
    {
          //Check effect of new inserted node
      arrangeNode(root);

      return true;
    }


  }
  return false;
}
void MaxHeap:: insert(int key)
{
        //Test case
  if(root==NULL)
  {
    root=new Node(key);
  }
  else if(root->left==NULL)
  {
    root->left = new Node(key);
    arrangeNode(root);

  }
  else if(root->right==NULL)
  {
    root->right = new Node(key);
    arrangeNode(root);
  }
  else
  {
    int height = insertHeight();

    addNode(root,height, 0,key);
  }
  this->size++;
}
void MaxHeap:: preorder(Node *root)
{
  if(root!=NULL)
  {
    cout<<"  "<<root->key;
    preorder(root->left);

    preorder(root->right);
  }
}
int main()
{
  MaxHeap heap1;

    //Construct first Max heap tree
  heap1.insert(5);
  heap1.insert(7);
  heap1.insert(4);
  heap1.insert(3);
  heap1.insert(9);
  heap1.insert(14);
  heap1.insert(2);
  heap1.insert(1);
  heap1.insert(6);
  heap1.insert(11);



  heap1.preorder(heap1.root);
    /*After insert element*/

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

    */



  MaxHeap heap2;

  //Construct second Min heap tree
  for (int i=15;i> 0;i-- ) 
  {
    heap2.insert(i);

  }

    /*After insert element*/

    /*
               15
           /       \
          /         \
         14          13
       /   \        /   \
      12    11     10    9
     / \    / \   / \    / \
    8   7  6   5 4   3  2   1
    */




  cout<<endl;

  heap2.preorder(heap2.root);
  return 0;
}

Output

  14  11  6  1  3  7  5  9  4  2
  15  14  12  8  7  11  6  5  13  10  4  3  9  2  1
/*
Java program
Binary Max Heap Tree Node Insertion
*/
//Tree node
class Node {
  //Left and right child
  public Node left;
  public Node right;

  //Data value
  public int key;

  public Node(int key) {
    this.key = key;

    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 insertHeight() {
    int i = 1;

    int sum = 0;

    while (this.size > sum + (1 << i)) {
      sum += (1 << i);
      i++;
    }
    return i;
  }
  public void swapNode(Node first, Node second) {
    int key = first.key;

    first.key = second.key;
    second.key = key;
  }
  //Arrange node key
  public void arrangeNode(Node root) {

    if (root.left != null && root.left.key > root.key) {
      swapNode(root, root.left);
    }
    if (root.right != null && root.right.key > root.key) {
      swapNode(root, root.right);
    }
  }
  public boolean addNode(Node root, int height, int level, int key) {
    if (level >= height) {
      return false;
    }
    if (root != null) {

      if (level - 1 == height && root.left == null || root.right == null) {
        if (root.left == null) {
          root.left = new Node(key);
        } else {
          root.right = new Node(key);
        }

        arrangeNode(root);

        return true;
      }

      if (addNode(root.left, height, level + 1, key) || addNode(root.right, height, level + 1, key)) {
        //Check effect of new inserted node
        arrangeNode(root);

        return true;
      }


    }
    return false;
  }
  //Handles the request to new inserting node
  public void insert(int key) {
    //Test case
    if (root == null) {
      root = new Node(key);
    } else if (root.left == null) {
      root.left = new Node(key);
      arrangeNode(root);

    } else if (root.right == null) {
      root.right = new Node(key);
      arrangeNode(root);
    } else {
      int height = insertHeight();

      addNode(root, height, 0, key);
    }
    this.size++;
  }

  public void preorder(Node root) {
    if (root != null) {
      System.out.print("  " + root.key);
      preorder(root.left);

      preorder(root.right);
    }
  }


  public static void main(String[] args) {

    MaxHeap heap1 = new MaxHeap();

    //Construct first Max heap tree
    heap1.insert(5);
    heap1.insert(7);
    heap1.insert(4);
    heap1.insert(3);
    heap1.insert(9);
    heap1.insert(14);
    heap1.insert(2);
    heap1.insert(1);
    heap1.insert(6);
    heap1.insert(11);

    heap1.preorder(heap1.root);
    /*After insert element*/

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



    MaxHeap heap2 = new MaxHeap();

    //Construct second Min heap tree
    for (int i = 15; i > 0; i--) {
      heap2.insert(i);
    }

    /*After insert element*/

    /*
               15
           /       \
          /         \
         14          13
       /   \        /   \
      12    11     10    9
     / \    / \   / \    / \
    8   7  6   5 4   3  2   1
    */




    System.out.println();

    heap2.preorder(heap2.root);

  }
}

Output

  14  11  6  1  3  7  5  9  4  2
  15  14  12  8  7  11  6  5  13  10  4  3  9  2  1
Binary max heap node insertion
/*
C# program
Binary Max Heap Tree Node Insertion
*/

using System;
//Tree node
public class Node {
	//Left and right child
	public Node left;
	public Node right;
	//Data value
	public int key;
	public Node(int key) {
		this.key = key;
		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 insertHeight() {
		int i = 1;
		int sum = 0;
		while (this.size > sum + (1 << i)) {
			sum += (1 << i);
			i++;
		}
		return i;
	}
	public void swapNode(Node first, Node second) {
		int key = first.key;
		first.key = second.key;
		second.key = key;
	}
	//Arrange node key
	public void arrangeNode(Node root) {
		if (root.left != null && root.left.key > root.key) {
			swapNode(root, root.left);
		}
		if (root.right != null && root.right.key > root.key) {
			swapNode(root, root.right);
		}
	}
	public Boolean addNode(Node root, int height, int level, int key) {
		if (level >= height) {
			return false;
		}
		if (root != null) {
			if (level - 1 == height && root.left == null || root.right == null) {
				if (root.left == null) {
					root.left = new Node(key);
				} else {
					root.right = new Node(key);
				}
				arrangeNode(root);
				return true;
			}
			if (addNode(root.left, height, level + 1, key) || 
                addNode(root.right, height, level + 1, key)) {
				arrangeNode(root);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	public void insert(int key) {
		//Test case

		if (root == null) {
			root = new Node(key);
		} else
		if (root.left == null) {
			root.left = new Node(key);
			arrangeNode(root);
		} else
		if (root.right == null) {
			root.right = new Node(key);
			arrangeNode(root);
		} else {
			int height = insertHeight();
			addNode(root, height, 0, key);
		}
		this.size++;
	}
	public void preorder(Node root) {
		if (root != null) {
			Console.Write(" " + root.key);
			preorder(root.left);
			preorder(root.right);
		}
	}
	public static void Main(String[] args) {
		MaxHeap heap1 = new MaxHeap();
		heap1.insert(5);
		heap1.insert(7);
		heap1.insert(4);
		heap1.insert(3);
		heap1.insert(9);
		heap1.insert(14);
		heap1.insert(2);
		heap1.insert(1);
		heap1.insert(6);
		heap1.insert(11);
		heap1.preorder(heap1.root);
		/*After insert element*/
		/*
		            14
		          /    \
		        11      9
		       /   \    /  \
		      6     7  4    2
		     / \   /
		    1   3 5
		    */
		MaxHeap heap2 = new MaxHeap();
		//Construct second Min heap tree

		for (int i = 15; i > 0; i--) {
			heap2.insert(i);
		}
		Console.WriteLine();
		heap2.preorder(heap2.root);
	}
}

Output

 14 11 6 1 3 7 5 9 4 2
 15 14 12 8 7 11 6 5 13 10 4 3 9 2 1
<?php
/*
Php program
Binary Max Heap Tree Node Insertion
*/
//Tree node
class Node {
	//Left and right child

	public $left;
	public $right;
	//Data value

	public $key;

	function __construct($key) {
		$this->key = $key;
		$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 insertHeight() {
		$i = 1;
		$sum = 0;
		while ($this->size > $sum + (1 << $i)) {
			$sum += (1 << $i);
			$i++;
		}
		return $i;
	}
	public 	function swapNode($first, $second) {
		$key = $first->key;
		$first->key = $second->key;
		$second->key = $key;
	}
	//Arrange node key

	public 	function arrangeNode($root) {
		if ($root->left != null && $root->left->key > $root->key) {
			$this->swapNode($root, $root->left);
		}
		if ($root->right != null && $root->right->key > $root->key) {
			$this->swapNode($root, $root->right);
		}
	}
	public 	function addNode($root, $height, $level, $key) {
		if ($level >= $height) {
			return false;
		}
		if ($root != null) {
			if ($level - 1 == $height && $root->left == null || $root->right == null) {
				if ($root->left == null) {
					$root->left = new Node($key);
				} else {
					$root->right = new Node($key);
				}
				$this->arrangeNode($root);
				return true;
			}
			if ($this->addNode($root->left, $height, $level + 1, $key) || 
                $this->addNode($root->right, $height, $level + 1, $key)) {
				//Check effect of new inserted node
				$this->arrangeNode($root);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node

	public 	function insert($key) {
		//Test case

		if ($this->root == null) {
			$this->root = new Node($key);
		} else
		if ($this->root->left == null) {
			$this->root->left = new Node($key);
			$this->arrangeNode($this->root);
		} else
		if ($this->root->right == null) {
			$this->root->right = new Node($key);
			$this->arrangeNode($this->root);
		} else {
			$height = $this->insertHeight();
			$this->addNode($this->root, $height, 0, $key);
		}
		$this->size++;
	}
	public 	function preorder($root) {
		if ($root != null) {
			echo(" ". $root->key);
			$this->preorder($root->left);
			$this->preorder($root->right);
		}
	}
}

function main() {
	$heap1 = new MaxHeap();
	//Construct first Max heap tree

	$heap1->insert(5);
	$heap1->insert(7);
	$heap1->insert(4);
	$heap1->insert(3);
	$heap1->insert(9);
	$heap1->insert(14);
	$heap1->insert(2);
	$heap1->insert(1);
	$heap1->insert(6);
	$heap1->insert(11);
	$heap1->preorder($heap1->root);
	/*After insert element*/
	/*
	            14
	          /    \
	        11      9
	       /   \    /  \
	      6     7  4    2
	     / \   /
	    1   3 5
	    */
	$heap2 = new MaxHeap();
	//Construct second Min heap tree

	for ($i = 15; $i > 0; $i--) {
		$heap2->insert($i);
	}
	/*After insert element*/
	/*
	               15
	           /       \
	          /         \
	         14          13
	       /   \        /   \
	      12    11     10    9
	     / \    / \   / \    / \
	    8   7  6   5 4   3  2   1
	    */

	echo ("\n");
	$heap2->preorder($heap2->root);

}
main();

Output

 14 11 6 1 3 7 5 9 4 2
 15 14 12 8 7 11 6 5 13 10 4 3 9 2 1
/*
Node Js program
Binary Max Heap Tree Node Insertion
*/
//Tree node
class Node {

	constructor(key) {
		this.key = key;
		this.left = null;
		this.right = null;
	}
}
class MaxHeap {
	
	constructor() {
		this.root = null;
		this.size = 0;
	}

	//Get height of insert new node
	insertHeight() {
		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;
	}

	//Arrange node key
	arrangeNode(root) {
		if (root.left != null && root.left.key > root.key) {
			this.swapNode(root, root.left);
		}

		if (root.right != null && root.right.key > root.key) {
			this.swapNode(root, root.right);
		}
	}
	addNode(root, height, level, key) {
		if (level >= height) {
			return false;
		}

		if (root != null) {
			if (level - 1 == height && root.left == null || root.right == null) {
				if (root.left == null) {
					root.left = new Node(key);
				} else {
					root.right = new Node(key);
				}
				this.arrangeNode(root);
				return true;
			}

			if (this.addNode(root.left, height, level + 1, key) || 
                this.addNode(root.right, height, level + 1, key)) {
				//Check effect of new inserted node
				this.arrangeNode(root);
				return true;
			}
		}

		return false;
	}

	//Handles the request to new inserting node
	insert(key) {
		//Test case

		if (this.root == null) {
			this.root = new Node(key);
		} else
		if (this.root.left == null) {
			this.root.left = new Node(key);
			this.arrangeNode(this.root);
		} else
		if (this.root.right == null) {
			this.root.right = new Node(key);
			this.arrangeNode(this.root);
		} else {
			var height = this.insertHeight();
			this.addNode(this.root, height, 0, key);
		}
		this.size++;
	}
	preorder(root) {
		if (root != null) {
			process.stdout.write(" " + root.key);
			this.preorder(root.left);
			this.preorder(root.right);
		}
	}
}

function main(args) {
	var heap1 = new MaxHeap();
	//Construct first Max heap tree
	heap1.insert(5);
	heap1.insert(7);
	heap1.insert(4);
	heap1.insert(3);
	heap1.insert(9);
	heap1.insert(14);
	heap1.insert(2);
	heap1.insert(1);
	heap1.insert(6);
	heap1.insert(11);
	heap1.preorder(heap1.root);
	/*After insert element*/
	/*
	            14
	          /    \
	        11      9
	       /   \    /  \
	      6     7  4    2
	     / \   /
	    1   3 5
	    */
	var heap2 = new MaxHeap();
	//Construct second Min heap tree

	for (var i = 15; i > 0; i--) {
		heap2.insert(i);
	}

	/*After insert element*/
	/*
	               15
	           /       \
	          /         \
	         14          13
	       /   \        /   \
	      12    11     10    9
	     / \    / \   / \    / \
	    8   7  6   5 4   3  2   1
	    */

	process.stdout.write("\n");
	heap2.preorder(heap2.root);
}

main();

Output

 14 11 6 1 3 7 5 9 4 2
 15 14 12 8 7 11 6 5 13 10 4 3 9 2 1
# Python 3 program
# Binary Max Heap Tree Node Insertion

# Tree node
class Node :
	def __init__(self, key) :
		self.key = key
		self.left = None
		self.right = None
	

class MaxHeap :

	def __init__(self) :
		self.root = None
		self.size = 0
	
	# Get height of insert new node
	def insertHeight(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
	
	# Arrange node key
	def arrangeNode(self, root) :
		if (root.left != None and root.left.key > root.key) :
			self.swapNode(root, root.left)
		
		if (root.right != None and root.right.key > root.key) :
			self.swapNode(root, root.right)
		
	
	def addNode(self, root, height, level, key) :
		if (level >= height) :
			return False
		
		if (root != None) :
			if (level - 1 == height and root.left == None or root.right == None) :
				if (root.left == None) :
					root.left = Node(key)
				else :
					root.right = Node(key)
				
				self.arrangeNode(root)
				return True
			
			if (self.addNode(root.left, height, level + 1, key) or self.addNode(root.right, height, level + 1, key)) :
				# Check effect of new inserted node
				self.arrangeNode(root)
				return True
			
		
		return False
	
	# Handles the request to new inserting node
	def insert(self, key) :
		# Test case
		if (self.root == None) :
			self.root = Node(key)
		elif (self.root.left == None) :
			self.root.left = Node(key)
			self.arrangeNode(self.root)
		elif (self.root.right == None) :
			self.root.right = Node(key)
			self.arrangeNode(self.root)
		else :
			height = self.insertHeight()
			self.addNode(self.root, height, 0, key)
		
		self.size += 1
	
	def preorder(self, root) :
		if (root != None) :
			print(" ", root.key, end = "")
			self.preorder(root.left)
			self.preorder(root.right)
		
	

def main() :
	heap1 = MaxHeap()
	# Construct first Max heap tree
	heap1.insert(5)
	heap1.insert(7)
	heap1.insert(4)
	heap1.insert(3)
	heap1.insert(9)
	heap1.insert(14)
	heap1.insert(2)
	heap1.insert(1)
	heap1.insert(6)
	heap1.insert(11)
	heap1.preorder(heap1.root)
	# After insert element
	 
	# 
	#             14
	#           /    \
	#         11      9
	#        /   \    /  \
	#       6     7  4    2
	#      / \   /
	#     1   3 5
	#     
	

	heap2 = MaxHeap()
	i = 15
	# Construct second Min heap tree
	while (i > 0) :
		heap2.insert(i)
		i -= 1
	
	print("\n", end = "")
	heap2.preorder(heap2.root)


if __name__ == "__main__":
	main()

Output

  14  11  6  1  3  7  5  9  4  2
  15  14  12  8  7  11  6  5  13  10  4  3  9  2  1
# Ruby program
# Binary Max Heap Tree Node Insertion

 # Tree node
class Node 
    # Define the accessor and reader of class Node
    attr_reader :left, :right, :key
    attr_accessor :left, :right, :key
	
	def initialize(key) 
		self.key = key
		@left = nil
		@right = nil
	end
end

class MaxHeap 
    # Define the accessor and reader of class MaxHeap
    attr_reader :size, :root
    attr_accessor :size, :root
	def initialize() 
		@root = nil
		@size = 0
	end
	 # Get height of insert new node
	def insertHeight() 
		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
	 # Arrange node key
	def arrangeNode(root) 
		if (root.left != nil && root.left.key > root.key) 
			self.swapNode(root, root.left)
		end
		if (root.right != nil && root.right.key > root.key) 
			self.swapNode(root, root.right)
		end
	end
	def addNode(root, height, level, key) 
		if (level >= height) 
			return false
		end
		if (root != nil) 
			if (level - 1 == height && root.left == nil || root.right == nil) 
				if (root.left == nil) 
					root.left = Node.new(key)
				else 
					root.right = Node.new(key)
				end
				self.arrangeNode(root)
				return true
			end
			if (self.addNode(root.left, height, level + 1, key) || 
                self.addNode(root.right, height, level + 1, key)) 
				 # Check effect of new inserted node
				self.arrangeNode(root)
				return true
			end
		end
		return false
	end
	 # Handles the request to new inserting node
	def insert(key) 
		 # Test case

		if (@root == nil) 
			@root = Node.new(key)
		elsif (@root.left == nil) 
			@root.left = Node.new(key)
			self.arrangeNode(@root)
		elsif (@root.right == nil) 
			@root.right = Node.new(key)
			self.arrangeNode(@root)
		else 
			height = self.insertHeight()
			self.addNode(@root, height, 0, key)
		end
		self.size += 1
	end
	def preorder(root) 
		if (root != nil) 
			print(" ", root.key)
			self.preorder(root.left)
			self.preorder(root.right)
		end
	end
end
def main() 
	heap1 = MaxHeap.new()
	 # Construct first Max heap tree
	heap1.insert(5)
	heap1.insert(7)
	heap1.insert(4)
	heap1.insert(3)
	heap1.insert(9)
	heap1.insert(14)
	heap1.insert(2)
	heap1.insert(1)
	heap1.insert(6)
	heap1.insert(11)
	heap1.preorder(heap1.root)
	# After insert element
	 
	# 
	#             14
	#           /    \
	#         11      9
	#        /   \    /  \
	#       6     7  4    2
	#      / \   /
	#     1   3 5
	#     
	
	heap2 = MaxHeap.new()
	i = 15
	 # Construct second Min heap tree
	while (i > 0) 
		heap2.insert(i)
		i -= 1
	end
	# After insert element
	 
	# 
	#                15
	#            /       \
	#           /         \
	#          14          13
	#        /   \        /   \
	#       12    11     10    9
	#      / \    / \   / \    / \
	#     8   7  6   5 4   3  2   1
	#     
	

	print("\n")
	heap2.preorder(heap2.root)
end


main()

Output

 14 11 6 1 3 7 5 9 4 2
 15 14 12 8 7 11 6 5 13 10 4 3 9 2 1
/*
Scala program
Binary Max Heap Tree Node Insertion
*/
//Tree node
class Node(var left: Node,
	var right: Node,
		var key: Int) {
	def this(key: Int) {
		this(null,null,key);
	}
} 
class MaxHeap(var size: Int,
		var root: Node) {

	def this() {
		this(0,null);
	}
	//Get height of insert new node
	def insertHeight(): Int = {
		var i: Int = 1;
		var sum: Int = 0;
		while (this.size > sum + (1 << i)) {
			sum += (1 << i);
			i += 1;
		}
		return i;
	}
	def swapNode(first: Node, second: Node): Unit = {
		val temp: Int = first.key;
		first.key = second.key;
		second.key = temp;
	}
	//Arrange node key
	def arrangeNode(root: Node): Unit = {
		if (root.left != null && root.left.key > root.key) {
			this.swapNode(root, root.left);
		}
		if (root.right != null && root.right.key > root.key) {
			this.swapNode(root, root.right);
		}
	}
	def addNode(root: Node, height: Int, level: Int, key: Int): Boolean = {
		if (level >= height) {
			return false;
		}
		if (root != null) {
			if (level - 1 == height && root.left == null || root.right == null) {
				if (root.left == null) {
					root.left = new Node(key);
				} else {
					root.right = new Node(key);
				}
				this.arrangeNode(root);

				return true;
			}
			if (this.addNode(root.left, height, level + 1, key) || 
                this.addNode(root.right, height, level + 1, key)) {
				//Check effect of new inserted node
				this.arrangeNode(root);

				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	def insert(key: Int): Unit = {
		//Test case

		if (this.root == null) {
			this.root = new Node(key);
		} else
		if (this.root.left == null) {
			this.root.left = new Node(key);
			this.arrangeNode(this.root);
		} else
		if (this.root.right == null) {
			this.root.right = new Node(key);
			this.arrangeNode(this.root);
		} else {
			val height: Int = this.insertHeight();
			this.addNode(this.root, height, 0, key);
		}
		this.size += 1;
	}
	def preorder(root: Node): Unit = {
		if (root != null) {
			print(" " + root.key);
			this.preorder(root.left);
			this.preorder(root.right);
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val heap1: MaxHeap = new MaxHeap();

		//Construct first Max heap tree
		heap1.insert(5);
		heap1.insert(7);
		heap1.insert(4);
		heap1.insert(3);
		heap1.insert(9);
		heap1.insert(14);
		heap1.insert(2);
		heap1.insert(1);
		heap1.insert(6);
		heap1.insert(11);
		heap1.preorder(heap1.root);

		/*After insert element*/
		/*
		            14
		          /    \
		        11      9
		       /   \    /  \
		      6     7  4    2
		     / \   /
		    1   3 5
		    */
		var heap2: MaxHeap = new MaxHeap();
		var i: Int = 15;

		//Construct second Min heap tree
		while (i > 0) {
			heap2.insert(i);
			i -= 1;
		}
		/*After insert element*/
		/*
		               15
		           /       \
		          /         \
		         14          13
		       /   \        /   \
		      12    11     10    9
		     / \    / \   / \    / \
		    8   7  6   5 4   3  2   1
		    */
		print("\n");
		heap2.preorder(heap2.root);
	}
}

Output

 14 11 6 1 3 7 5 9 4 2
 15 14 12 8 7 11 6 5 13 10 4 3 9 2 1
/*
Swift program
Binary Max Heap Tree Node Insertion
*/
//Tree node
class Node {
	var left: Node? ;
	var right: Node? ;
	var key: Int;
	init(_ key: Int) {
		self.key = key;
		left = nil;
		right = nil;
	}
}
class MaxHeap {
	var size: Int;
	var root: Node? ;
	init() {
		root = nil;
		size = 0;
	}
	//Get height of insert new node
	func insertHeight() -> Int {
		var i = 1;
		var sum = 0;
		while (self.size > sum + (1 << i)) {
			sum += (1 << i);
			i += 1;
		}
		return i;
	}
	func swapNode(_ first: Node? , _ second : Node? ) {
		let temp = first!.key;
		first!.key = second!.key;
		second!.key = temp;
	}
	//Arrange node key
	func arrangeNode(_ root: Node? ) {
		if (root!.left != nil && root!.left!.key > root!.key) {
			self.swapNode(root, root!.left);
		}
		if (root!.right != nil && root!.right!.key > root!.key) {
			self.swapNode(root, root!.right);
		}
	}
	func addNode(_ root: Node? , _ height : Int, _ level: Int, _ key: Int) -> Bool {
		if (level >= height) {
			return false;
		}
		if (root != nil) {
			if (level - 1 == height && root!.left == nil || root!.right == nil) {
				if (root!.left == nil) {
					root!.left = Node(key);
				} else {
					root!.right = Node(key);
				}
				self.arrangeNode(root);
				return true;
			}
			if (self.addNode(root!.left, height, level + 1, key) || 
                self.addNode(root!.right, height, level + 1, key)) {
				//Check effect of new inserted node
				self.arrangeNode(root);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	func insert(_ key: Int) {
		//Test case

		if (root == nil) {
			root = Node(key);
		} else
		if (root!.left == nil) {
			root!.left = Node(key);
			self.arrangeNode(root);
		} else
		if (root!.right == nil) {
			root!.right = Node(key);
			self.arrangeNode(root);
		} else {
			let height = self.insertHeight();
			let _ = self.addNode(root, height, 0, key);
		}
		self.size += 1;
	}
	func preorder(_ root: Node? ) {
		if (root != nil) {
			print(" ", root!.key, terminator: "");
			self.preorder(root!.left);
			self.preorder(root!.right);
		}
	}
}
func main() {
	let heap1 : MaxHeap? = MaxHeap();
	//Construct first Max heap tree
	heap1!.insert(5);
	heap1!.insert(7);
	heap1!.insert(4);
	heap1!.insert(3);
	heap1!.insert(9);
	heap1!.insert(14);
	heap1!.insert(2);
	heap1!.insert(1);
	heap1!.insert(6);
	heap1!.insert(11);
	heap1!.preorder(heap1!.root);
	/*After insert element*/
	/*
	            14
	          /    \
	        11      9
	       /   \    /  \
	      6     7  4    2
	     / \   /
	    1   3 5
	    */
	let heap2 : MaxHeap? = MaxHeap();
	var i = 15;
	//Construct second Min heap tree
	while (i > 0) {
		heap2!.insert(i);
		i -= 1;
	}
	print("\n", terminator: "");
	heap2!.preorder(heap2!.root);
}
main();

Output

  14  11  6  1  3  7  5  9  4  2
  15  14  12  8  7  11  6  5  13  10  4  3  9  2  1


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

New Comment







© 2021, kalkicode.com, All rights reserved