Merge two Binary Max Heap Tree

/*
  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