# How to Merge two binary Max Heaps in C++

Hey! In this tutorial, we are going to learn how to merge two binary Max Heaps in C++. Before the actual procedure, We will be learning what are Max heaps, what does Binary Max heap refer to? How to implement Binary Max heap for a given array and finally we will learn how to merge two binary Max Heaps using C++ Programming.

## Merge two binary max heaps and learning the basic definition of heaps

Firstly, we shall understand what heaps are. A heap is a special Tree-Based Data Structure where the tree is complete Binary Tree. A complete Binary tree is a data structure in which every internal node must have exactly two children and the leaf nodes can have either two children or left child only. (If it has to be Complete Binary Tree, leaf nodes can not have the right child without having a corresponding left child.) Major applications of the heap are Heap Sort and Priority Queue.

There are two types of Binary Heaps:

- Max Binary Heap – Heap structure in which the root node is greater than or equal to any of the nodes in the subtree and the same goes for every node and its corresponding subtree.

- Min Binary Heap – Heap structure in which the root node is smaller than or equal to any of the nodes in the subtree and the same goes for every node and its corresponding subtree.

#### Our approach to merge two binary max heap will be:

We will copy both the given max binary heap arrays into one array which will take O(n) time complexity and then we will implement a max-heap structure for that given array, which we also call as heapify. The time complexity of heapifying in a tight case is O(n). so our overall complexity of the theorem will be O(n) which is quite satisfying. When we call on the heapify function, it will create a max heap for us using recursion and stores it in the array itself. Our approach is to find the last non-leaf node and then perform heapify in reverse order on each non-leaf node. The index of the last non-leaf node is given by **(n/2)-1 **where n is the number of nodes.

To build the max heap we will call heapify only on the non-leaf nodes i.e. nodes on the left of the index **(n/2)-1 **in the given array.

Let’s now implement our code for the same:

#include <iostream> using namespace std; // Helper function to heapify. void helper(int mergedArray[], int size, int currentNodeIndex) { int rootIndex = currentNodeIndex; // Initialize currentNodeIndex as rootNodeIndex for current subtree. int leftChildIndex = 2 * currentNodeIndex + 1; // Finding leftchildIndex of current Node = 2*currentNodeIndex + 1 int rightChildIndex = 2 * currentNodeIndex + 2; // Finding rightchildIndex of current node= 2*currenNodeIndex + 2 // If left child is greater, make it root. if (leftChildIndex < size && mergedArray[leftChildIndex] > mergedArray[rootIndex]) rootIndex = leftChildIndex; // If right child is greater, make it root. if (rightChildIndex < size && mergedArray[rightChildIndex] > mergedArray[rootIndex]) rootIndex = rightChildIndex; // Swapping of root if not the largest. if (rootIndex != currentNodeIndex) { swap(mergedArray[currentNodeIndex], mergedArray[rootIndex]); // Recursively calling helper function on subtree. helper(mergedArray, size, rootIndex); } } // Heapify function. void heapify(int mergedArray[], int size) { // Index of last non-leaf node int lastindex = (size / 2) - 1; // Performing heapify in reverse order for every index less than last leaf node index. for (int i = lastindex; i >= 0; i--) { helper(mergedArray, size, i); } } void copyArrays(int* mergedArray, int* A1, int* A2, int m, int n) { // Copy elements of both array to new array. for (int i = 0; i < m; i++) mergedArray[i] = A1[i]; for (int i = 0; i < n; i++) mergedArray[m + i] = A2[i]; // finally calling on heapify function. heapify(mergedArray, m+n); } int main() { int A1[] = { 20, 6, 9, 33, 88, 56, 79 }; int A2[] = { 81, 100, 45, 37, 11, 67 }; int m = sizeof(A1)/sizeof(A1[0]); //finding the size of first array. int n = sizeof(A2)/sizeof(A2[0]); //finding the size of second array. int* mergedArray = new int[m+n]; //declaring a new array to copy elements copyArrays(mergedArray,A1,A2,m,n); cout<<"After merging two max heaps into one we get:"<<endl; for (int i = 0; i < m+n ; i++) cout << mergedArray[i] << " "; return 0; }

Output :

After merging two max heaps into one we get: 100 88 79 81 45 67 9 6 33 20 37 11 56

Thank You.

Article on Heap Sort: Perform Heap Sort in C++

## Leave a Reply