Merge Two Sorted Arrays Using a Priority Queue

Introduction

This blog will discuss the solution to this problem to merge two sorted arrays using a priority queue. Before we deep dive into this problem, look at Understanding Merge Two Sorted Arrays for better clarity for this particular problem.

Some Examples

Input:

A[] = {1, 2, 5, 10}, B[] = {1, 3, 4, 10}

Output: 

{1, 1, 2, 3, 4, 5, 10}

Input:

A[] = {2, 4, 7, 9, 10}, B[] = {1 , 5, 6, 11}

Output:

{1, 2, 4, 5, 7, 9, 10, 11}

Recommended: Before stepping towards the approach of  Merge two sorted arrays try it by yourself on Coding Ninjas Studio.

Priority Queue Approach

To solve this problem, merge two sorted arrays using a  priority queue. We will create a min priority queue, and we will push elements of both the array. After that, we will take out elements from the priority queue one by one, and we will insert that element into our final array, and then we will return the array. 

Algorithm

1. To solve this problem, merge sorted arrays using a priority queue. We first need to create a function mergeTwoArrays() that takes two parameters: the first array and the second array.
2. In the function, we will declare a priority queue that will store all the elements of both arrays. 
3. We will now take out the top element of the priority queue one by one and store it in the final array till the priority queue is not empty.
4. Now we will return the array.

Code in C++

// C++ code to Merge two sorted arrays using a Priority queue
#include <bits/stdc++.h>
using namespace std;

// function to merge two sorted arrays using a priority queue
vector<int> mergeTwoArrays(vector<int> A, vector<int> B)
{
    // taking the size of both the arrays
    int n1 = A.size(), n2 = B.size();
    // to store the answer
    vector<int> ans(n1 + n2);

    // the top element is minimum among all the elements
    priority_queue<int, vector<int>, greater<int>> p;

    // storing all the elements of the first array
    for (int i = 0; i < n1; i++)
    {
        p.push(A[i]);
    }

    // storing all the elements of the second array
    for (int i = 0; i < n2; i++)
    {
        p.push(B[i]);
    }

    int index = 0;
    while (!p.empty())
    {
        // arranging the elements of both the
        // arrays in increasing fashion
        ans[index] = p.top();
        index++;
        p.pop();
    }
    return ans;
}

// Driver Code
int main()
{

    int n1 = 4, n2 = 5;
    vector<int> arr1(n1), arr2(n2);
    arr1 = {1, 5, 10, 15};
    arr2 = {2, 4, 6, 8, 10};

    vector<int> ans = mergeTwoArrays(arr1, arr2);
    cout << "{";
    for (int i = 0; i < n1 + n2 - 1; i++)
    {
        cout << ans[i] << ", ";
    }
    cout << ans[n1 + n2 - 1] << "}";
}

 

You can also try this code with Online C++ Compiler

Run Code

Input and Ouptut:

Input: A[] = {1, 5, 10, 15}, B[] = {2, 4, 6, 8, 10}

Output: {1, 2, 4, 5, 6, 8, 10, 10, 15}

You can also try this code with Online C++ Compiler

Run Code

Complexity Analysis

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

Since the time complexity needed to maintain a priority queue is O(N*log(N)), we use a priority queue of size N+M. Therefore the time complexity will be O((N+M)* log(N+M)).

Space Complexity: O(N+M)

Since we store our answer in another array, we are storing all the elements of both the array. Therefore the space complexity will be O(N+M).

Also Read, Prefix Sum Array