Skip to main content

Merge two Binary Max Heap Tree

Here given code implementation process.

/*
  C++ program
  Merge two Binary Max Heap Tree
*/
//Tree node
#include<iostream>

using namespace std;
class Node {
	public:

	//Left and right child
	Node *left;
	Node *right;
	//Data value
	int key;
	Node(int key) {
		this->key = key;
		this->left = NULL;
		this->right = NULL;
	}
};
class MaxHeap {
	public:

	//This is use to store information of number of nodes in Max heap
	int size;
	Node *root;
	MaxHeap() {
		this->root = NULL;
		this->size = 0;
	}
	//Get height of insert new node
	int insert_height() {
		int i = 1;
		int sum = 0;
		while (this->size > sum + (1 << i)) {
			sum += (1 << i);
			i++;
		}
		return i;
	}
	void swap_node(Node *first, Node *second) {
		int key = first->key;
		first->key = second->key;
		second->key = key;
	}
	//Arrange node key
	void arrange_node(Node *root) {
		if (root->left != NULL && root->left->key > root->key) {
			this->swap_node(root, root->left);
		}
		if (root->right != NULL && root->right->key > root->key) {
			this->swap_node(root, root->right);
		}
	}
	bool add_node(Node *root, int height, int level, Node *newNode) {
		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;
				} else {
					root->right = newNode;
				}
				this->arrange_node(root);
				return true;
			}
			if (this->add_node(root->left, height, level + 1, newNode) || this->add_node(root->right, height, level + 1, newNode)) {
				//Check effect of new inserted node
				this->arrange_node(root);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	void insert(int key) {
		if (this->root == NULL) {
			this->root = new Node(key);
		} else
		if (this->root->left == NULL) {
			this->root->left = new Node(key);
			this->arrange_node(this->root);
		} else
		if (this->root->right == NULL) {
			this->root->right = new Node(key);
			this->arrange_node(this->root);
		} else {
			int height = this->insert_height();
			Node *newNode = new Node(key);
			this->add_node(this->root, height, 0, newNode);
		}
		this->size++;
	}
	Node *combine(MaxHeap first, MaxHeap second, Node *root) {
		if (root != NULL) {
			root->left = this->combine(first, second, root->left);
			root->right = this->combine(first, second, root->right);
			if (root->left == NULL && root->right == NULL) {
				int height = first.insert_height();
				//add node in first tree
				this->add_node(first.root, height, 0, root);
				first.size++;
				second.size--;
				return NULL;
			}
		}
		return root;
	}
	void merge(MaxHeap heap2) {
		if (this->root != NULL && heap2.root != NULL) {
			if (this->size > heap2.size) {
				cout << "\n\n Merging of heap 2 in heap 1 ";
				//add node element in first tree
				heap2.root = this->combine(*this, heap2, heap2.root);
			} else {
				cout << "\n\n Merging of heap 1 in heap 2 ";
				//add node element in second tree
				this->root = this->combine(heap2, *this, this->root);
			}
		}
	}
	void preorder(Node *root) {
		if (root != NULL) {
			cout << " " << root->key;
			this->preorder(root->left);
			this->preorder(root->right);
		}
	}
	void inorder(Node *root) {
		if (root != NULL) {
			this->inorder(root->left);
			cout << " " << root->key;
			this->inorder(root->right);
		}
	}
	void postorder(Node *root) {
		if (root != NULL) {
			this->postorder(root->left);
			this->postorder(root->right);
			cout << " " << root->key;
		}
	}
	void print_nodes() {
		cout << "\nPreorder : \n";
		this->preorder(this->root);
		cout << "\nInorder : \n";
		this->inorder(this->root);
		cout << "\nPostorder : \n";
		this->postorder(this->root);
	}
};
int main() {
	MaxHeap heap1 = MaxHeap();
	//Construct first Max heap tree
	heap1.insert(8);
	heap1.insert(10);
	heap1.insert(14);
	heap1.insert(13);
	heap1.insert(11);
	heap1.insert(12);
	/*After insert element*/
	/*
	                 14
	               /    \
	              13     12 
	            /  \    /  
	           8   11 10  
	       
	      Preorder : 
	        14  13  8  11  12  10
	      Inorder : 
	        8  13  11  14  10  12
	      Postorder : 
	        8  11  13  10  12  14



	    */
	MaxHeap heap2 = MaxHeap();
	//Construct second max heap tree

	for (int i = 7; i > 0; i--) {
		heap2.insert(i);
	}
	/*After insert element*/
	/*
	                7
	             /    \
	            /      \
	           6        5 
	         /   \     /  \
	        4     3   2    1


	    Preorder : 
	      7  6  4  3  5  2  1
	    Inorder : 
	      4  6  3  7  2  5  1
	    Postorder : 
	      4  3  6  2  1  5  7


	    */

	cout << "First heap element : \n";
	heap1.print_nodes();
	cout << "\n\nSecond heap element : \n";
	heap2.print_nodes();
	heap1.merge(heap2);
	cout << "\n After Merges ";
	/*After Merge element*/
	/*
	                   14
	               /       \
	              /         \
	             11           13
	           /   \         /  \
	          7     10      12    1
	         / \    / \    /  \
	        4   6  3   8  2    5

	      Preorder : 
	        14  11  7  4  6  10  3  8  13  12  2  5  1
	      Inorder : 
	        4  7  6  11  3  10  8  14  2  12  5  13  1
	      Postorder : 
	        4  6  7  3  8  10  11  2  5  12  1  13  14
	    */

	if (heap1.root != NULL) {
		cout << "\n\nFirst heap element : ";
		heap1.print_nodes();
	}
	if (heap2.root != NULL) {
		cout << "\n\nSecond heap element : \n";
		heap2.print_nodes();
	}
	return 0;
}

Output

First heap element :

Preorder :
 14 13 8 11 12 10
Inorder :
 8 13 11 14 10 12
Postorder :
 8 11 13 10 12 14

Second heap element :

Preorder :
 7 6 4 3 5 2 1
Inorder :
 4 6 3 7 2 5 1
Postorder :
 4 3 6 2 1 5 7

 Merging of heap 1 in heap 2
 After Merges

Second heap element :

Preorder :
 14 11 7 4 6 10 3 8 13 12 2 5 1
Inorder :
 4 7 6 11 3 10 8 14 2 12 5 13 1
Postorder :
 4 6 7 3 8 10 11 2 5 12 1 13 14
/*
  Java program
  Merge two Binary Max Heap Tree
*/
//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 insert_height()
    {
      int i=1;

      int sum=0;

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

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

      if(root.left!=null && root.left.key > root.key)
      {
        swap_node(root,root.left);
      }
      if(root.right!=null && root.right.key > root.key)
      {
        swap_node(root,root.right);
      }
    }
   public boolean  add_node(Node root, int height ,int level,Node newNode)
   {
     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;
        }
        else
        {
          root.right=newNode;
        }

        arrange_node(root);

        return true;
      }

      if(add_node(root.left, height, level+1,newNode) || 
         add_node(root.right, height,level+1,newNode))
      {
          //Check effect of new inserted node
        arrange_node(root);

        return true;
      }


    }
    return false;
  }
  //Handles the request to new inserting node
  public void insert(int key)
  {

    if(root==null)
    {
      root=new Node(key);
    }
    else if(root.left==null)
    {
      root.left = new Node(key);
      arrange_node(root);

    }
    else if(root.right==null)
    {
      root.right = new Node(key);
      arrange_node(root);
    }
    else
    {
      int height = insert_height();
      Node newNode=new Node(key);
      add_node(root,height, 0,newNode);
    }
    this.size++;
  }
  public Node combine(MaxHeap first,MaxHeap second ,Node root)
  {

    if(root!=null)
    {
      root.left=combine(first,second,root.left);
      root.right=combine(first,second,root.right);

      if(root.left==null && root.right==null)
      {

        int height = first.insert_height();
          //add node in first tree
        add_node(first.root,height, 0,root);
        first.size++;
        second.size--;
        return null;
      }
    }
    return root;
  }
  public void merge(MaxHeap heap2)
  {

    if(this.root !=null && heap2.root!=null)
    {
      if(this.size>heap2.size)
      {
        System.out.print("\n\n Merging of heap 2 in heap 1 ");
              //add node element in first tree
        heap2.root=combine(this,heap2,heap2.root);
      }
      else
      {
        System.out.print("\n\n Merging of heap 1 in heap 2 ");
              //add node element in second tree
        this.root=combine(heap2,this,this.root);
      }
    }
  }

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

      inorder(root.left);
      System.out.print("  "+root.key);
      inorder(root.right);
    }
  }

  public void postorder(Node root)
  {
    if(root!=null)
    {

      postorder(root.left);

      postorder(root.right);
      System.out.print("  "+root.key);
    }
  }
  public void print_nodes()
  {
    System.out.print("\nPreorder : \n" );
    preorder(this.root);
    System.out.print("\nInorder : \n" );
    inorder(this.root);
    System.out.print("\nPostorder : \n" );
    postorder(this.root);
  }



  public static void main(String[] args) 
  {

    MaxHeap heap1= new MaxHeap();

    //Construct first Max heap tree
    heap1.insert(8);
    heap1.insert(10);
    heap1.insert(14);
    heap1.insert(13);
    heap1.insert(11);
    heap1.insert(12);

    /*After insert element*/

    /*
                 14
               /    \
              13     12 
            /  \    /  
           8   11 10  
       
      Preorder : 
        14  13  8  11  12  10
      Inorder : 
        8  13  11  14  10  12
      Postorder : 
        8  11  13  10  12  14



    */



    MaxHeap heap2 = new MaxHeap();

    //Construct second max heap tree
    int i = 7;
    while (i > 0) {
      heap2.insert(i);
      i--;
    }

    /*After insert element*/

    /*
                7
             /    \
            /      \
           6        5 
         /   \     /  \
        4     3   2    1


    Preorder : 
      7  6  4  3  5  2  1
    Inorder : 
      4  6  3  7  2  5  1
    Postorder : 
      4  3  6  2  1  5  7


    */

    System.out.print("First heap element : \n" );

    heap1.print_nodes();


    System.out.print("\n\nSecond heap element : \n" );
    heap2.print_nodes();



    heap1.merge(heap2);



    System.out.print("\n  After Merges ");


    /*After Merge element*/

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

      Preorder : 
        14  11  7  4  6  10  3  8  13  12  2  5  1
      Inorder : 
        4  7  6  11  3  10  8  14  2  12  5  13  1
      Postorder : 
        4  6  7  3  8  10  11  2  5  12  1  13  14
    */
    if(heap1.root!=null)
    {
      System.out.print("\n\nFirst heap element : " );
      heap1.print_nodes();
    }    
    if(heap2.root!=null)
    {
      System.out.print("\n\nSecond heap element : \n" );
      heap2.print_nodes();
    }


  }
}

Output

First heap element :

Preorder :
  14  13  8  11  12  10
Inorder :
  8  13  11  14  10  12
Postorder :
  8  11  13  10  12  14

Second heap element :

Preorder :
  7  6  4  3  5  2  1
Inorder :
  4  6  3  7  2  5  1
Postorder :
  4  3  6  2  1  5  7

 Merging of heap 1 in heap 2
 After Merges

Second heap element :

Preorder :
  14  11  7  4  6  10  3  8  13  12  2  5  1
Inorder :
  4  7  6  11  3  10  8  14  2  12  5  13  1
Postorder :
  4  6  7  3  8  10  11  2  5  12  1  13  14
/*
  C# program
  Merge two Binary Max Heap Tree
*/
//Tree node
using System;
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 insert_height() {
		int i = 1;
		int sum = 0;
		while (this.size > sum + (1 << i)) {
			sum += (1 << i);
			i++;
		}
		return i;
	}
	public void swap_node(Node first, Node second) {
		int data = first.key;
		first.key = second.key;
		second.key = data;
	}
	//Arrange node key
	public void arrange_node(Node root) {
		if (root.left != null && root.left.key > root.key) {
			swap_node(root, root.left);
		}
		if (root.right != null && root.right.key > root.key) {
			swap_node(root, root.right);
		}
	}
	public Boolean add_node(Node root, int height, int level, Node newNode) {
		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;
				} else {
					root.right = newNode;
				}
				arrange_node(root);
				return true;
			}
			if (add_node(root.left, height, level + 1, newNode) || 
                add_node(root.right, height, level + 1, newNode)) {
				arrange_node(root);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	public void insert(int key) {
		if (root == null) {
			root = new Node(key);
		} else
		if (root.left == null) {
			root.left = new Node(key);
			arrange_node(root);
		} else
		if (root.right == null) {
			root.right = new Node(key);
			arrange_node(root);
		} else {
			int height = insert_height();
			Node newNode = new Node(key);
			add_node(root, height, 0, newNode);
		}
		this.size++;
	}
	public Node combine(MaxHeap first, MaxHeap second, Node root) {
		if (root != null) {
			root.left = combine(first, second, root.left);
			root.right = combine(first, second, root.right);
			if (root.left == null && root.right == null) {
				int height = first.insert_height();
				add_node(first.root, height, 0, root);
				first.size++;
				second.size--;
				return null;
			}
		}
		return root;
	}
	public void merge(MaxHeap heap2) {
		if (this.root != null && heap2.root != null) {
			if (this.size > heap2.size) {
				Console.Write("\n\n Merging of heap 2 in heap 1 ");
				//add node element in first tree
				heap2.root = combine(this, heap2, heap2.root);
			} else {
				Console.Write("\n\n Merging of heap 1 in heap 2 ");
				//add node element in second tree
				this.root = combine(heap2, this, this.root);
			}
		}
	}
	public void preorder(Node root) {
		if (root != null) {
			Console.Write(" " + root.key);
			preorder(root.left);
			preorder(root.right);
		}
	}
	public void inorder(Node root) {
		if (root != null) {
			inorder(root.left);
			Console.Write(" " + root.key);
			inorder(root.right);
		}
	}
	public void postorder(Node root) {
		if (root != null) {
			postorder(root.left);
			postorder(root.right);
			Console.Write(" " + root.key);
		}
	}
	public void print_nodes() {
		Console.Write("\nPreorder : \n");
		preorder(this.root);
		Console.Write("\nInorder : \n");
		inorder(this.root);
		Console.Write("\nPostorder : \n");
		postorder(this.root);
	}
	public static void Main(String[] args) {
		MaxHeap heap1 = new MaxHeap();
		heap1.insert(8);
		heap1.insert(10);
		heap1.insert(14);
		heap1.insert(13);
		heap1.insert(11);
		heap1.insert(12);
		/*After insert element*/
		/*
		                 14
		               /    \
		              13     12 
		            /  \    /  
		           8   11 10  
		       
		      Preorder : 
		        14  13  8  11  12  10
		      Inorder : 
		        8  13  11  14  10  12
		      Postorder : 
		        8  11  13  10  12  14



		    */
		MaxHeap heap2 = new MaxHeap();
		//Construct second max heap tree

		for (int i = 7; i > 0; i--) {
			heap2.insert(i);
		}
		Console.Write("First heap element : \n");
		heap1.print_nodes();
		Console.Write("\n\nSecond heap element : \n");
		heap2.print_nodes();
		heap1.merge(heap2);
		Console.Write("\n After Merges ");
		/*After Merge element*/
		/*
		                   14
		               /       \
		              /         \
		             11           13
		           /   \         /  \
		          7     10      12    1
		         / \    / \    /  \
		        4   6  3   8  2    5

		      Preorder : 
		        14  11  7  4  6  10  3  8  13  12  2  5  1
		      Inorder : 
		        4  7  6  11  3  10  8  14  2  12  5  13  1
		      Postorder : 
		        4  6  7  3  8  10  11  2  5  12  1  13  14
		    */

		if (heap1.root != null) {
			Console.Write("\n\nFirst heap element : ");
			heap1.print_nodes();
		}
		if (heap2.root != null) {
			Console.Write("\n\nSecond heap element : \n");
			heap2.print_nodes();
		}
	}
}

Output

First heap element :

Preorder :
 14 13 8 11 12 10
Inorder :
 8 13 11 14 10 12
Postorder :
 8 11 13 10 12 14

Second heap element :

Preorder :
 7 6 4 3 5 2 1
Inorder :
 4 6 3 7 2 5 1
Postorder :
 4 3 6 2 1 5 7

 Merging of heap 1 in heap 2
 After Merges

Second heap element :

Preorder :
 14 11 7 4 6 10 3 8 13 12 2 5 1
Inorder :
 4 7 6 11 3 10 8 14 2 12 5 13 1
Postorder :
 4 6 7 3 8 10 11 2 5 12 1 13 14
<?php
/*
  Php program
  Merge two Binary Max Heap Tree
*/
//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 insert_height() {
		$i = 1;
		$sum = 0;
		while ($this->size > $sum + (1 << $i)) {
			$sum += (1 << $i);
			$i++;
		}
		return $i;
	}
	public 	function swap_node($first, $second) {
		$data = $first->key;
		$first->key = $second->key;
		$second->key = $data;
	}
	//Arrange node key

	public 	function arrange_node($root) {
		if ($root->left != null && $root->left->key > $root->key) {
			$this->swap_node($root, $root->left);
		}
		if ($root->right != null && $root->right->key > $root->key) {
			$this->swap_node($root, $root->right);
		}
	}
	public 	function add_node($root, $height, $level, $newNode) {
		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;
				} else {
					$root->right = $newNode;
				}
				$this->arrange_node($root);
				return true;
			}
			if ($this->add_node($root->left, $height, $level + 1, $newNode) || $this->add_node($root->right, $height, $level + 1, $newNode)) {
				//Check effect of new inserted node
				$this->arrange_node($root);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node

	public 	function insert($key) {
		if ($this->root == null) {
			$this->root = new Node($key);
		} else
		if ($this->root->left == null) {
			$this->root->left = new Node($key);
			$this->arrange_node($this->root);
		} else
		if ($this->root->right == null) {
			$this->root->right = new Node($key);
			$this->arrange_node($this->root);
		} else {
			$height = $this->insert_height();
			$newNode = new Node($key);
			$this->add_node($this->root, $height, 0, $newNode);
		}
		$this->size++;
	}
	public 	function combine($first, $second, $root) {
		if ($root != null) {
			$root->left = $this->combine($first, $second, $root->left);
			$root->right = $this->combine($first, $second, $root->right);
			if ($root->left == null && $root->right == null) {
				$height =
					$first->insert_height();
				//add node in first tree
				$this->add_node($first->root, $height, 0, $root);
				$first->size++;
				$second->size--;
				return null;
			}
		}
		return $root;
	}
	public 	function merge($heap2) {
		if ($this->root != null && $heap2->root != null) {
			if ($this->size > $heap2->size) {
				echo("\n\n Merging of heap 2 in heap 1 ");
				//add node element in first tree
				$heap2->root = $this->combine($this, $heap2, $heap2->root);
			} else {
				echo("\n\n Merging of heap 1 in heap 2 ");
				//add node element in second tree
				$this->root = $this->combine($heap2, $this, $this->root);
			}
		}
	}
	public 	function preorder($root) {
		if ($root != null) {
			echo(" ". $root->key);
			$this->preorder($root->left);
			$this->preorder($root->right);
		}
	}
	public 	function inorder($root) {
		if ($root != null) {
			$this->inorder($root->left);
			echo(" ". $root->key);
			$this->inorder($root->right);
		}
	}
	public 	function postorder($root) {
		if ($root != null) {
			$this->postorder($root->left);
			$this->postorder($root->right);
			echo(" ". $root->key);
		}
	}
	public 	function print_nodes() {
		echo("\nPreorder : \n");
		$this->preorder($this->root);
		echo("\nInorder : \n");
		$this->inorder($this->root);
		echo("\nPostorder : \n");
		$this->postorder($this->root);
	}
}

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

	$heap1->insert(8);
	$heap1->insert(10);
	$heap1->insert(14);
	$heap1->insert(13);
	$heap1->insert(11);
	$heap1->insert(12);
	/*After insert element*/
	/*
	                 14
	               /    \
	              13     12 
	            /  \    /  
	           8   11 10  
	       
	      Preorder : 
	        14  13  8  11  12  10
	      Inorder : 
	        8  13  11  14  10  12
	      Postorder : 
	        8  11  13  10  12  14



	    */
	$heap2 = new MaxHeap();
	//Construct second max heap tree

	for ($i = 7; $i > 0; $i--) {
		$heap2->insert($i);
	}
	/*After insert element*/
	/*
	                7
	             /    \
	            /      \
	           6        5 
	         /   \     /  \
	        4     3   2    1


	    Preorder : 
	      7  6  4  3  5  2  1
	    Inorder : 
	      4  6  3  7  2  5  1
	    Postorder : 
	      4  3  6  2  1  5  7


	    */

	echo("First heap element : \n");
	$heap1->print_nodes();
	echo("\n\nSecond heap element : \n");
	$heap2->print_nodes();
	$heap1->merge($heap2);
	echo("\n After Merges ");
	/*After Merge element*/
	/*
	                   14
	               /       \
	              /         \
	             11           13
	           /   \         /  \
	          7     10      12    1
	         / \    / \    /  \
	        4   6  3   8  2    5

	      Preorder : 
	        14  11  7  4  6  10  3  8  13  12  2  5  1
	      Inorder : 
	        4  7  6  11  3  10  8  14  2  12  5  13  1
	      Postorder : 
	        4  6  7  3  8  10  11  2  5  12  1  13  14
	    */

	if ($heap1->root != null) {
		echo("\n\nFirst heap element : ");
		$heap1->print_nodes();
	}
	if ($heap2->root != null) {
		echo("\n\nSecond heap element : \n");
		$heap2->print_nodes();
	}

}
main();

Output

First heap element :

Preorder :
 14 13 8 11 12 10
Inorder :
 8 13 11 14 10 12
Postorder :
 8 11 13 10 12 14

Second heap element :

Preorder :
 7 6 4 3 5 2 1
Inorder :
 4 6 3 7 2 5 1
Postorder :
 4 3 6 2 1 5 7

 Merging of heap 1 in heap 2
 After Merges

Second heap element :

Preorder :
 14 11 7 4 6 10 3 8 13 12 2 5 1
Inorder :
 4 7 6 11 3 10 8 14 2 12 5 13 1
Postorder :
 4 6 7 3 8 10 11 2 5 12 1 13 14
/*
  Node Js program
  Merge two Binary Max Heap Tree
*/
//Tree node
class Node {
	
	constructor(key) {
		this.key = key;
		this.left = null;
		this.right = null;
	}
}
class MaxHeap {
	
	constructor() {
		this.root = null;
     	//This is use to store information of number of nodes in Max heap
		this.size = 0;
	}

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

		return i;
	}
	swap_node(first, second) {
		var data = first.key;
		first.key = second.key;
		second.key = data;
	}

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

		if (root.right != null && root.right.key > root.key) {
			this.swap_node(root, root.right);
		}
	}
	add_node(root, height, level, newNode) {
		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;
				} else {
					root.right = newNode;
				}
				this.arrange_node(root);
				return true;
			}

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

		return false;
	}

	//Handles the request to new inserting node
	insert(key) {
		if (this.root == null) {
			this.root = new Node(key);
		} else
		if (this.root.left == null) {
			this.root.left = new Node(key);
			this.arrange_node(this.root);
		} else
		if (this.root.right == null) {
			this.root.right = new Node(key);
			this.arrange_node(this.root);
		} else {
			var height = this.insert_height();
			var newNode = new Node(key);
			this.add_node(this.root, height, 0, newNode);
		}
		this.size++;
	}
	combine(first, second, root) {
		if (root != null) {
			root.left = this.combine(first, second, root.left);
			root.right = this.combine(first, second, root.right);
			if (root.left == null && root.right == null) {
				var height = first.insert_height();
				//add node in first tree
				this.add_node(first.root, height, 0, root);
				first.size++;
				second.size--;
				return null;
			}
		}

		return root;
	}
	merge(heap2) {
		if (this.root != null && heap2.root != null) {
			if (this.size > heap2.size) {
				process.stdout.write("\n\n Merging of heap 2 in heap 1 ");
				//add node element in first tree
				heap2.root = this.combine(this, heap2, heap2.root);
			} else {
				process.stdout.write("\n\n Merging of heap 1 in heap 2 ");
				//add node element in second tree
				this.root = this.combine(heap2, this, this.root);
			}
		}
	}
	preorder(root) {
		if (root != null) {
			process.stdout.write(" " + root.key);
			this.preorder(root.left);
			this.preorder(root.right);
		}
	}
	inorder(root) {
		if (root != null) {
			this.inorder(root.left);
			process.stdout.write(" " + root.key);
			this.inorder(root.right);
		}
	}
	postorder(root) {
		if (root != null) {
			this.postorder(root.left);
			this.postorder(root.right);
			process.stdout.write(" " + root.key);
		}
	}
	print_nodes() {
		process.stdout.write("\nPreorder : \n");
		this.preorder(this.root);
		process.stdout.write("\nInorder : \n");
		this.inorder(this.root);
		process.stdout.write("\nPostorder : \n");
		this.postorder(this.root);
	}
}

function main(args) {
	var heap1 = new MaxHeap();
	//Construct first Max heap tree
	heap1.insert(8);
	heap1.insert(10);
	heap1.insert(14);
	heap1.insert(13);
	heap1.insert(11);
	heap1.insert(12);
	/*After insert element*/
	/*
	                 14
	               /    \
	              13     12 
	            /  \    /  
	           8   11 10  
	       
	      Preorder : 
	        14  13  8  11  12  10
	      Inorder : 
	        8  13  11  14  10  12
	      Postorder : 
	        8  11  13  10  12  14



	    */
	var heap2 = new MaxHeap();
	//Construct second max heap tree

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

	/*After insert element*/
	/*
	                7
	             /    \
	            /      \
	           6        5 
	         /   \     /  \
	        4     3   2    1


	    Preorder : 
	      7  6  4  3  5  2  1
	    Inorder : 
	      4  6  3  7  2  5  1
	    Postorder : 
	      4  3  6  2  1  5  7


	    */

	process.stdout.write("First heap element : \n");
	heap1.print_nodes();
	process.stdout.write("\n\nSecond heap element : \n");
	heap2.print_nodes();
	heap1.merge(heap2);
	process.stdout.write("\n After Merges ");
	/*After Merge element*/
	/*
	                   14
	               /       \
	              /         \
	             11           13
	           /   \         /  \
	          7     10      12    1
	         / \    / \    /  \
	        4   6  3   8  2    5

	      Preorder : 
	        14  11  7  4  6  10  3  8  13  12  2  5  1
	      Inorder : 
	        4  7  6  11  3  10  8  14  2  12  5  13  1
	      Postorder : 
	        4  6  7  3  8  10  11  2  5  12  1  13  14
	    */

	if (heap1.root != null) {
		process.stdout.write("\n\nFirst heap element : ");
		heap1.print_nodes();
	}

	if (heap2.root != null) {
		process.stdout.write("\n\nSecond heap element : \n");
		heap2.print_nodes();
	}
}

main();

Output

First heap element :

Preorder :
 14 13 8 11 12 10
Inorder :
 8 13 11 14 10 12
Postorder :
 8 11 13 10 12 14

Second heap element :

Preorder :
 7 6 4 3 5 2 1
Inorder :
 4 6 3 7 2 5 1
Postorder :
 4 3 6 2 1 5 7

 Merging of heap 1 in heap 2
 After Merges

Second heap element :

Preorder :
 14 11 7 4 6 10 3 8 13 12 2 5 1
Inorder :
 4 7 6 11 3 10 8 14 2 12 5 13 1
Postorder :
 4 6 7 3 8 10 11 2 5 12 1 13 14
#  Python 3 program
#  Merge two Binary Max Heap Tree

# Tree node

class Node :
	# Left and right child  # Data value 
	def __init__(self, key) :
		self.key = key
		self.left = None
		self.right = None
	

class MaxHeap :
	# This is use to store information of number of nodes in Max heap 
	def __init__(self) :
		self.root = None
		self.size = 0
	 # Get height of insert new node
	def insert_height(self) :
		i = 1
		sum = 0
		while (self.size > sum + (1 << i)) :
			sum += (1 << i)
			i += 1
		
		return i
	
	def swap_node(self, first, second) :
		data = first.key
		first.key = second.key
		second.key = data
	 # Arrange node key
	def arrange_node(self, root) :
		if (root.left != None and root.left.key > root.key) :
			self.swap_node(root, root.left)
		
		if (root.right != None and root.right.key > root.key) :
			self.swap_node(root, root.right)
		
	
	def add_node(self, root, height, level, newNode) :
		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 = newNode
				else :
					root.right = newNode
				
				self.arrange_node(root)
				return True
			
			if (self.add_node(root.left, height, level + 1, newNode) or 
                self.add_node(root.right, height, level + 1, newNode)) :
				# Check effect of new inserted node
				self.arrange_node(root)
				return True
			
		
		return False
	 # Handles the request to new inserting node
	def insert(self, key) :
		if (self.root == None) :
			self.root = Node(key)
		elif (self.root.left == None) :
			self.root.left = Node(key)
			self.arrange_node(self.root)
		elif (self.root.right == None) :
			self.root.right = Node(key)
			self.arrange_node(self.root)
		else :
			height = self.insert_height()
			newNode = Node(key)
			self.add_node(self.root, height, 0, newNode)
		
		self.size += 1
	
	def combine(self, first, second, root) :
		if (root != None) :
			root.left = self.combine(first, second, root.left)
			root.right = self.combine(first, second, root.right)
			if (root.left == None and root.right == None) :
				height = first.insert_height() # add node in first tree
				self.add_node(first.root, height, 0, root)
				first.size += 1
				second.size -= 1
				return None
			
		
		return root
	
	def merge(self, heap2) :
		if (self.root != None and heap2.root != None) :
			if (self.size > heap2.size) :
				print("\n\n Merging of heap 2 in heap 1 ", end = "") 
				# add node element in first tree
				heap2.root = self.combine(self, heap2, heap2.root)
			else :
				print("\n\n Merging of heap 1 in heap 2 ", end = "") 
				# add node element in second tree
				self.root = self.combine(heap2, self, self.root)
			
		
	
	def preorder(self, root) :
		if (root != None) :
			print(" ", root.key, end = "")
			self.preorder(root.left)
			self.preorder(root.right)
		
	
	def inorder(self, root) :
		if (root != None) :
			self.inorder(root.left)
			print(" ", root.key, end = "")
			self.inorder(root.right)
		
	
	def postorder(self, root) :
		if (root != None) :
			self.postorder(root.left)
			self.postorder(root.right)
			print(" ", root.key, end = "")
		
	
	def print_nodes(self) :
		print("\nPreorder : \n", end = "")
		self.preorder(self.root)
		print("\nInorder : \n", end = "")
		self.inorder(self.root)
		print("\nPostorder : \n", end = "")
		self.postorder(self.root)
	

def main() :
	heap1 = MaxHeap() # Construct first Max heap tree
	heap1.insert(8)
	heap1.insert(10)
	heap1.insert(14)
	heap1.insert(13)
	heap1.insert(11)
	heap1.insert(12)
	#
	#                 14
	#               /    \
	#              13     12 
	#            /  \    /  
	#           8   11 10  
	#       
	#      Preorder : 
	#        14  13  8  11  12  10
	#      Inorder : 
	#        8  13  11  14  10  12
	#      Postorder : 
	#        8  11  13  10  12  14
	#    
	
	#After insert element
	 
	#
	#                 14
	#               /    \
	#              13     12 
	#            /  \    /  
	#           8   11 10  
	#       
	#      Preorder : 
	#        14  13  8  11  12  10
	#      Inorder : 
	#        8  13  11  14  10  12
	#      Postorder : 
	#        8  11  13  10  12  14
	#    
	

	heap2 = MaxHeap() # Construct second max heap tree
	i = 7
	while (i > 0) :
		heap2.insert(i)
		i -= 1
	
	print("First heap element : \n", end = "")
	heap1.print_nodes()
	print("\n\nSecond heap element : \n", end = "")
	heap2.print_nodes()
	heap1.merge(heap2)
	print("\n After Merges ", end = "")
	#
	#                   14
	#               /       \
	#              /         \
	#             11           13
	#           /   \         /  \
	#          7     10      12    1
	#         / \    / \    /  \
	#        4   6  3   8  2    5
	#      Preorder : 
	#        14  11  7  4  6  10  3  8  13  12  2  5  1
	#      Inorder : 
	#        4  7  6  11  3  10  8  14  2  12  5  13  1
	#      Postorder : 
	#        4  6  7  3  8  10  11  2  5  12  1  13  14
	#    
	
	#After Merge element
	 
	#
	#                   14
	#               /       \
	#              /         \
	#             11           13
	#           /   \         /  \
	#          7     10      12    1
	#         / \    / \    /  \
	#        4   6  3   8  2    5
	#      Preorder : 
	#        14  11  7  4  6  10  3  8  13  12  2  5  1
	#      Inorder : 
	#        4  7  6  11  3  10  8  14  2  12  5  13  1
	#      Postorder : 
	#        4  6  7  3  8  10  11  2  5  12  1  13  14
	#    
	


	if (heap1.root != None) :
		print("\n\nFirst heap element : ", end = "")
		heap1.print_nodes()
	
	if (heap2.root != None) :
		print("\n\nSecond heap element : \n", end = "")
		heap2.print_nodes()
	


if __name__ == "__main__":
	main()

Output

First heap element :

Preorder :
  14  13  8  11  12  10
Inorder :
  8  13  11  14  10  12
Postorder :
  8  11  13  10  12  14

Second heap element :

Preorder :
  7  6  4  3  5  2  1
Inorder :
  4  6  3  7  2  5  1
Postorder :
  4  3  6  2  1  5  7

 Merging of heap 1 in heap 2
 After Merges

Second heap element :

Preorder :
  14  11  7  4  6  10  3  8  13  12  2  5  1
Inorder :
  4  7  6  11  3  10  8  14  2  12  5  13  1
Postorder :
  4  6  7  3  8  10  11  2  5  12  1  13  14
#  Ruby program
#  Merge two Binary Max Heap Tree

 # 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 insert_height() 
		i = 1
		sum = 0
		while (self.size > sum + (1 << i)) 
			sum += (1 << i)
			i += 1
		end
		return i
	end
	def swap_node(first, second) 
		data = first.key
		first.key = second.key
		second.key = data
	end
	 # Arrange node key
	def arrange_node(root) 
		if (root.left != nil && root.left.key > root.key) 
			self.swap_node(root, root.left)
		end
		if (root.right != nil && root.right.key > root.key) 
			self.swap_node(root, root.right)
		end
	end
	def add_node(root, height, level, newNode) 
		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 = newNode
				else 
					root.right = newNode
				end
				self.arrange_node(root)
				return true
			end
			if (self.add_node(root.left, height, level + 1, newNode) || 
                self.add_node(root.right, height, level + 1, newNode)) 
				 # Check effect of new inserted node
				self.arrange_node(root)
				return true
			end
		end
		return false
	end
	 # Handles the request to new inserting node
	def insert(key) 
		if (@root == nil) 
			@root = Node.new(key)
		elsif (@root.left == nil) 
			@root.left = Node.new(key)
			self.arrange_node(@root)
		elsif (@root.right == nil) 
			@root.right = Node.new(key)
			self.arrange_node(@root)
		else 
			height = self.insert_height()
			newNode = Node.new(key)
			self.add_node(@root, height, 0, newNode)
		end
		self.size += 1
	end
	def combine(first, second, root) 
		if (root != nil) 
			root.left = self.combine(first, second, root.left)
			root.right = self.combine(first, second, root.right)
			if (root.left == nil && root.right == nil) 
				height = first.insert_height()
				 # add node in first tree
				self.add_node(first.root, height, 0, root)
				first.size += 1
				second.size -= 1
				return nil
			end
		end
		return root
	end
	def merge(heap2) 
		if (self.root != nil && heap2.root != nil) 
			if (self.size > heap2.size) 
				print("\n\n Merging of heap 2 in heap 1 ")
				 # add node element in first tree
				heap2.root = self.combine(self, heap2, heap2.root)
			else 
				print("\n\n Merging of heap 1 in heap 2 ")
				 # add node element in second tree
				self.root = self.combine(heap2, self, self.root)
			end
		end
	end
	def preorder(root) 
		if (root != nil) 
			print(" ", root.key)
			self.preorder(root.left)
			self.preorder(root.right)
		end
	end
	def inorder(root) 
		if (root != nil) 
			self.inorder(root.left)
			print(" ", root.key)
			self.inorder(root.right)
		end
	end
	def postorder(root) 
		if (root != nil) 
			self.postorder(root.left)
			self.postorder(root.right)
			print(" ", root.key)
		end
	end
	def print_nodes() 
		print("\nPreorder  :\n")
		self.preorder(self.root)
		print("\nInorder  :\n")
		self.inorder(self.root)
		print("\nPostorder  :\n")
		self.postorder(self.root)
	end
end
def main() 
	heap1 = MaxHeap.new()
	 # Construct first Max heap tree
	heap1.insert(8)
	heap1.insert(10)
	heap1.insert(14)
	heap1.insert(13)
	heap1.insert(11)
	heap1.insert(12)
	#After insert element
	 
	#
	#                 14
	#               /    \
	#              13     12 
	#            /  \    /  
	#           8   11 10  
	#       
	#      Preorder  :
	#        14  13  8  11  12  10
	#      Inorder  :
	#        8  13  11  14  10  12
	#      Postorder  :
	#        8  11  13  10  12  14
	#    
	
	heap2 = MaxHeap.new()
	 # Construct second max heap tree
	i = 7
	while (i > 0) 
		heap2.insert(i)
		i -= 1
	end
	#After insert element
	 
	#
	#                7
	#             /    \
	#            /      \
	#           6        5 
	#         /   \     /  \
	#        4     3   2    1
	#    Preorder  :
	#      7  6  4  3  5  2  1
	#    Inorder  :
	#      4  6  3  7  2  5  1
	#    Postorder  :
	#      4  3  6  2  1  5  7
	#    
	

	print("First heap element  :\n")
	heap1.print_nodes()
	print("\n\nSecond heap element  :\n")
	heap2.print_nodes()
	heap1.merge(heap2)
	print("\n After Merges ")
	#After Merge element
	 
	#
	#                   14
	#               /       \
	#              /         \
	#             11           13
	#           /   \         /  \
	#          7     10      12    1
	#         / \    / \    /  \
	#        4   6  3   8  2    5
	#      Preorder  :
	#        14  11  7  4  6  10  3  8  13  12  2  5  1
	#      Inorder  :
	#        4  7  6  11  3  10  8  14  2  12  5  13  1
	#      Postorder  :
	#        4  6  7  3  8  10  11  2  5  12  1  13  14
	#    
	

	if (heap1.root != nil) 
		print("\n\nFirst heap element  :")
		heap1.print_nodes()
	end
	if (heap2.root != nil) 
		print("\n\nSecond heap element  :\n")
		heap2.print_nodes()
	end
end


main()

Output

First heap element  :

Preorder  :
 14 13 8 11 12 10
Inorder  :
 8 13 11 14 10 12
Postorder  :
 8 11 13 10 12 14

Second heap element  :

Preorder  :
 7 6 4 3 5 2 1
Inorder  :
 4 6 3 7 2 5 1
Postorder  :
 4 3 6 2 1 5 7

 Merging of heap 1 in heap 2 
 After Merges 

Second heap element  :

Preorder  :
 14 11 7 4 6 10 3 8 13 12 2 5 1
Inorder  :
 4 7 6 11 3 10 8 14 2 12 5 13 1
Postorder  :
 4 6 7 3 8 10 11 2 5 12 1 13 14
/*
  Scala program
  Merge two Binary Max Heap Tree
*/
//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 insert_height(): Int = {
		var i: Int = 1;
		var sum: Int = 0;
		while (this.size > sum + (1 << i)) {
			sum += (1 << i);
			i += 1;
		}
		return i;
	}
	def swap_node(first: Node, second: Node): Unit = {
		val data: Int = first.key;
		first.key = second.key;
		second.key = data;
	}
	//Arrange node key
	def arrange_node(root: Node): Unit = {
		if (root.left != null && root.left.key > root.key) {
			this.swap_node(root, root.left);
		}
		if (root.right != null && root.right.key > root.key) {
			this.swap_node(root, root.right);
		}
	}
	def add_node(root: Node, height: Int, level: Int, newNode: Node): 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 = newNode;
				} else {
					root.right = newNode;
				}
				this.arrange_node(root);

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

				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	def insert(key: Int): Unit = {
		if (this.root == null) {
			this.root = new Node(key);
		} else
		if (this.root.left == null) {
			this.root.left = new Node(key);
			this.arrange_node(this.root);
		} else
		if (this.root.right == null) {
			this.root.right = new Node(key);
			this.arrange_node(this.root);
		} else {
			var height: Int = this.insert_height();
			var newNode: Node = new Node(key);
			this.add_node(this.root, height, 0, newNode);
		}
		this.size += 1;
	}
	def combine(first: MaxHeap, second: MaxHeap, root: Node): Node = {
		if (root != null) {
			root.left = this.combine(first, second, root.left);
			root.right = this.combine(first, second, root.right);

			if (root.left == null && root.right == null) {
				val height: Int = first.insert_height();

				//add node in first tree
				this.add_node(first.root, height, 0, root);
				first.size += 1;
				second.size -= 1;

				return null;
			}
		}
		return root;
	}
	def merge(heap2: MaxHeap): Unit = {
		if (this.root != null && heap2.root != null) {
			if (this.size > heap2.size) {
				print("\n\n Merging of heap 2 in heap 1 ");

				//add node element in first tree
				heap2.root = this.combine(this, heap2, heap2.root);
			} else {
				print("\n\n Merging of heap 1 in heap 2 ");

				//add node element in second tree
				this.root = this.combine(heap2, this, this.root);
			}
		}
	}
	def preorder(root: Node): Unit = {
		if (root != null) {
			print(" " + root.key);
			this.preorder(root.left);
			this.preorder(root.right);
		}
	}
	def inorder(root: Node): Unit = {
		if (root != null) {
			this.inorder(root.left);
			print(" " + root.key);
			this.inorder(root.right);
		}
	}
	def postorder(root: Node): Unit = {
		if (root != null) {
			this.postorder(root.left);
			this.postorder(root.right);
			print(" " + root.key);
		}
	}
	def print_nodes(): Unit = {
		print("\nPreorder : \n");
		this.preorder(this.root);
		print("\nInorder : \n");
		this.inorder(this.root);
		print("\nPostorder : \n");
		this.postorder(this.root);
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val heap1: MaxHeap = new MaxHeap();

		//Construct first Max heap tree
		heap1.insert(8);
		heap1.insert(10);
		heap1.insert(14);
		heap1.insert(13);
		heap1.insert(11);
		heap1.insert(12);

		/*After insert element*/
		/*
		                 14
		               /    \
		              13     12 
		            /  \    /  
		           8   11 10  
		       
		      Preorder : 
		        14  13  8  11  12  10
		      Inorder : 
		        8  13  11  14  10  12
		      Postorder : 
		        8  11  13  10  12  14



		    */
		var heap2: MaxHeap = new MaxHeap();

		//Construct second max heap tree
		var i: Int = 7;
		while (i > 0) {
			heap2.insert(i);
			i -= 1;
		}
		/*After insert element*/
		/*
		                7
		             /    \
		            /      \
		           6        5 
		         /   \     /  \
		        4     3   2    1


		    Preorder : 
		      7  6  4  3  5  2  1
		    Inorder : 
		      4  6  3  7  2  5  1
		    Postorder : 
		      4  3  6  2  1  5  7


		    */
		print("First heap element : \n");
		heap1.print_nodes();
		print("\n\nSecond heap element : \n");
		heap2.print_nodes();
		heap1.merge(heap2);
		print("\n After Merges ");

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

		      Preorder : 
		        14  11  7  4  6  10  3  8  13  12  2  5  1
		      Inorder : 
		        4  7  6  11  3  10  8  14  2  12  5  13  1
		      Postorder : 
		        4  6  7  3  8  10  11  2  5  12  1  13  14
		    */

		if (heap1.root != null) {
			print("\n\nFirst heap element : ");
			heap1.print_nodes();
		}
		if (heap2.root != null) {
			print("\n\nSecond heap element : \n");
			heap2.print_nodes();
		}
	}
}

Output

First heap element :

Preorder :
 14 13 8 11 12 10
Inorder :
 8 13 11 14 10 12
Postorder :
 8 11 13 10 12 14

Second heap element :

Preorder :
 7 6 4 3 5 2 1
Inorder :
 4 6 3 7 2 5 1
Postorder :
 4 3 6 2 1 5 7

 Merging of heap 1 in heap 2
 After Merges

Second heap element :

Preorder :
 14 11 7 4 6 10 3 8 13 12 2 5 1
Inorder :
 4 7 6 11 3 10 8 14 2 12 5 13 1
Postorder :
 4 6 7 3 8 10 11 2 5 12 1 13 14
/*
  Swift program
  Merge two Binary Max Heap Tree
*/
//Tree node
class Node {
	
	//Left and right child
	var	left : Node?;
	var right : Node?;
	//Data value
	var	key : Int;
	init(_ key: Int) {
		self.key = key;
		self.left = nil;
		self.right = nil;
	}
}
class MaxHeap {
	
	//This is use to store information of number of nodes in Max heap
	var	size : Int;
	var root : Node?;
	init() {
		self.root = nil;
		self.size = 0;
	}
	//Get height of insert new node
	func insert_height() -> Int {
		var i = 1;
		var sum = 0;
		while (self.size > sum + (1 << i)) {
			sum += (1 << i);
			i += 1;
		}
		return i;
	}
	func swap_node(_ first: Node?, _ second: Node?) {
		let data = first!.key;
		first!.key = second!.key;
		second!.key = data;
	}
	//Arrange node key
	func arrange_node(_ root: Node?) {
		if (root!.left != nil && root!.left!.key > root!.key) {
			self.swap_node(root, root!.left);
		}
		if (root!.right != nil && root!.right!.key > root!.key) {
			self.swap_node(root, root!.right);
		}
	}
	func add_node(_ root: Node?, _ height: Int, _ level: Int, _ newNode: Node?) -> 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 = newNode;
				} else {
					root!.right = newNode;
				}
				self.arrange_node(root);
				return true;
			}
			if (self.add_node(root!.left, height, level + 1, newNode) || 
                self.add_node(root!.right, height, level + 1, newNode)) {
				//Check effect of new inserted node
				self.arrange_node(root);
				return true;
			}
		}
		return false;
	}
	//Handles the request to new inserting node
	func insert(_ key: Int) {
		if (self.root == nil) {
			self.root = Node(key);
		} else
		if (self.root!.left == nil) {
			self.root!.left = Node(key);
			self.arrange_node(self.root);
		} else
		if (self.root!.right == nil) {
			self.root!.right = Node(key);
			self.arrange_node(self.root);
		} else {
			let height = self.insert_height();
			let newNode = Node(key);
			let _ = self.add_node(self.root, height, 0, newNode);
		}
		self.size += 1;
	}
	func combine(_ first: MaxHeap, _ second: MaxHeap, _ root: Node?) -> Node? {
		if (root != nil) {
			root!.left = self.combine(first, second, root!.left);
			root!.right = self.combine(first, second, root!.right);
			if (root!.left == nil && root!.right == nil) {
				let height = first.insert_height();
				//add node in first tree
				let _ = self.add_node(first.root, height, 0, root);
				first.size += 1;
				second.size -= 1;
				return nil;
			}
		}
		return root;
	}
	func merge(_ heap2: MaxHeap) {
		if (self.root != nil && heap2.root != nil) {
			if (self.size > heap2.size) {
				print("\n\n Merging of heap 2 in heap 1 ", terminator: "");
				//add node element in first tree
				heap2.root = self.combine(self, heap2, heap2.root);
			} else {
				print("\n\n Merging of heap 1 in heap 2 ", terminator: "");
				//add node element in second tree
				self.root = self.combine(heap2, self, self.root);
			}
		}
	}
	func preorder(_ root: Node?) {
		if (root != nil) {
			print(" ", root!.key, terminator: "");
			self.preorder(root!.left);
			self.preorder(root!.right);
		}
	}
	func inorder(_ root: Node?) {
		if (root != nil) {
			self.inorder(root!.left);
			print(" ", root!.key, terminator: "");
			self.inorder(root!.right);
		}
	}
	func postorder(_ root: Node?) {
		if (root != nil) {
			self.postorder(root!.left);
			self.postorder(root!.right);
			print(" ", root!.key, terminator: "");
		}
	}
	func print_nodes() {
		print("\nPreorder : \n", terminator: "");
		self.preorder(self.root);
		print("\nInorder : \n", terminator: "");
		self.inorder(self.root);
		print("\nPostorder : \n", terminator: "");
		self.postorder(self.root);
	}
}
func main() {
	let heap1 = MaxHeap();
	//Construct first Max heap tree
	heap1.insert(8);
	heap1.insert(10);
	heap1.insert(14);
	heap1.insert(13);
	heap1.insert(11);
	heap1.insert(12);
	/*After insert element*/
	/*
	                 14
	               /    \
	              13     12 
	            /  \    /  
	           8   11 10  
	       
	      Preorder : 
	        14  13  8  11  12  10
	      Inorder : 
	        8  13  11  14  10  12
	      Postorder : 
	        8  11  13  10  12  14



	    */
	let heap2 = MaxHeap();
	//Construct second max heap tree
	var i = 7;
	while (i > 0) {
		heap2.insert(i);
		i -= 1;
	}
	print("First heap element : \n", terminator: "");
	heap1.print_nodes();
	print("\n\nSecond heap element : \n", terminator: "");
	heap2.print_nodes();
	heap1.merge(heap2);
	print("\n After Merges ", terminator: "");
	/*After Merge element*/
	/*
	                   14
	               /       \
	              /         \
	             11           13
	           /   \         /  \
	          7     10      12    1
	         / \    / \    /  \
	        4   6  3   8  2    5

	      Preorder : 
	        14  11  7  4  6  10  3  8  13  12  2  5  1
	      Inorder : 
	        4  7  6  11  3  10  8  14  2  12  5  13  1
	      Postorder : 
	        4  6  7  3  8  10  11  2  5  12  1  13  14
	    */

	if (heap1.root != nil) {
		print("\n\nFirst heap element : ", terminator: "");
		heap1.print_nodes();
	}
	if (heap2.root != nil) {
		print("\n\nSecond heap element : \n", terminator: "");
		heap2.print_nodes();
	}
}
main();

Output

First heap element :

Preorder :
  14  13  8  11  12  10
Inorder :
  8  13  11  14  10  12
Postorder :
  8  11  13  10  12  14

Second heap element :

Preorder :
  7  6  4  3  5  2  1
Inorder :
  4  6  3  7  2  5  1
Postorder :
  4  3  6  2  1  5  7

 Merging of heap 1 in heap 2
 After Merges

Second heap element :

Preorder :
  14  11  7  4  6  10  3  8  13  12  2  5  1
Inorder :
  4  7  6  11  3  10  8  14  2  12  5  13  1
Postorder :
  4  6  7  3  8  10  11  2  5  12  1  13  14




Comment

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

New Comment