Heap: Given two max heaps, merge them

Problem Statement:

You are given 2 max heaps.

You need to merge them into a single max heap

Example:

Solution 1: Using Priority Queue

Take a pq.

Then add all the elements from the both of the arrays in PQ to arrive at the solution.

Time Complexity: O((N + M)*log(N + M))
Space Complexity: O((N + M))

Solution 2:

Create a new array by merging the both the arrays and then call the heapify method from the last leaf node to arrive at the solution.

Time Complexity: O(N + M)
Space Complexity: O(N + M)

Code Solution

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void maxHeapify(vector<int>& arr, int n, int i)
{

    if (i >= n)
        return;

    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int max = i;

    if (l < n && arr[l] > arr[i])
        max = l;
    if (r < n && arr[r] > arr[max])
        max = r;

    if (max != i) 
    {
        swap(arr[max], arr[i]);
        maxHeapify(arr, n, max);
    }
}


vector<int> solution_2 (vector<int>& a, vector<int>& b)
{

    vector<int> merged;

    for(auto i:a)
    	merged.push_back(i);

    for(auto i:b)
    	merged.push_back(i);

    int size = merged.size();

    for (int i = size / 2 - 1; i >= 0; i--)
        maxHeapify(merged, size, i);

    return merged;
}


vector<int> solution_1(vector<int>& a, vector<int>& b)
{
    priority_queue<int> maxHeap;

    for (int i = 0; i < a.size(); i++) 
    {
        maxHeap.push(a[i]);
    }

    for (int i = 0; i < b.size(); i++) 
    {
        maxHeap.push(b[i]);
    }

    vector<int> merged;

    while (!maxHeap.empty()) 
    {
        merged.push_back(maxHeap.top());
        maxHeap.pop();
    }
    return merged;
}



int main()
{
    vector<int> a = { 12, 7, 8, 4 };
    vector<int> b = { 14, 9, 11 };
    
    int n = a.size();
    int m = b.size();
        
    vector<int> merged = solution_1(a, b);

    for (int i = 0; i < n + m; i++)
        cout << merged[i] << " ";

    a = { 12, 7, 8, 4 };
    b = { 14, 9, 11 };
    
	merged = solution_2(a, b);
    cout<<endl;
    for (int i = 0; i < n + m; i++)
        cout << merged[i] << " ";

    return 0;
}

Output

14 12 11 9 8 7 4 
14 12 11 4 7 9 8