Merge two Binary Min Heap Tree

/*
  C++ program
  Merge two Binary Min 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 MinHeap {
  public:

  //This is use to store information of number of nodes in Min heap
  int size;
  Node *root;
  MinHeap() {
    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(MinHeap first, MinHeap second, Node *root) {
    if (root != NULL) {
      root->left = first.combine(first, second, root->left);
      root->right = first.combine(first, second, root->right);
      if (root->left == NULL && root->right == NULL) {
        int height = first.insert_height();
        //add node in first tree
        first.add_node(first.root, height, 0, root);
        first.size++;
        second.size--;
        return NULL;
      }
    }
    return root;
  }
  void merge(MinHeap 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
       // cout<<this->root<<endl;
        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);
        //   cout<<heap2.root->key<<endl;
      }
    }
  }
  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_data()
  {
    cout << "\nPreorder : \n";
    preorder(this->root);
    cout << "\nInorder : \n";
    inorder(this->root);
    cout << "\nPostorder : \n";
    postorder(this->root);
  }
};
int main() {
  MinHeap heap1 = MinHeap();

  //Construct first Min heap tree
  heap1.insert(8);
  heap1.insert(10);
  heap1.insert(14);
  heap1.insert(13);
  heap1.insert(11);
  heap1.insert(12);
  /*After insert element*/
  /*
               8
             /    \
            10     12 
          /  \    /  
         13   11 14  
     
    Preorder : 
      8  10  13  11  12  14
    Inorder : 
      13  10  11  8  14  12
    Postorder : 
      13  11  10  14  12  8


      */
  MinHeap heap2 = MinHeap();
  //Construct second Min heap tree

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


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

    */

  cout << "First heap element : \n";
  heap1.print_data();
  cout << "\n\nSecond heap element : \n";
  heap2.print_data();


  heap1.merge(heap2);

  cout << "\n After Merges ";
  /*After Merge element*/
  /*
                     1
                 /       \
                /         \
               4            2
             /   \         /  \
            7     5       6    3
           / \    /\     /  \
          13  11 10 14  12   8

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

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

Output

First heap element :

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

Second heap element :

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

 Merging of heap 1 in heap 2
 After Merges

Second heap element :

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