## 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

- 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.
- In the function, we will declare a priority queue that will store all the elements of both arrays.
- 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.
- 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] << "}";
}
```

**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}
```

### 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__