Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Some Examples
2.
Priority Queue Approach
2.1.
Algorithm
2.2.
Code in C++
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is a heap?
3.2.
What is a priority queue?
3.3.
What is the difference between a min priority queue and a priority queue?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Merge Two Sorted Arrays Using a Priority Queue

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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}

illustration

 

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] << "}";
}

 

 

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a heap?

Heap is a tree-based data structure. More precisely, it is a particular case of a balanced binary tree that stores the tree’s nodes in a specific order. 

What is a priority queue?

The priority queue is similar to the regular queue. The only difference is that the priority queue stores elements in a particular order of priority, where the top element has the highest priority.

What is the difference between a min priority queue and a priority queue?

The only difference between the priority queue and the min priority queue is that the top element of the priority queue is maximum among all the elements, whereas the top element of the min priority queue is minimum among all the elements.

Conclusion

This article discussed the problem of merging two sorted arrays using a priority queue. We have discussed its approach based on the priority queue, and we have also discussed the time and space complexities of the approach.

We hope you have gained a better understanding of the solution to this problem. Now it is your responsibility to solve the problem and try new and different approaches.

Refer to Top Array Interview Questions, Heap and Priority Queue, Application of Priority Queue, and Arrays to better understand these data structures used in this particular problem.

I hope that this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem and if you would like to learn more, check out our articles on the Coding Ninjas Studio. Enroll in our courses, refer to the test series and problems available, and look at the problems, interview experiences, and interview bundle for placement preparations for big tech companies like Amazon, Microsoft, Google, etc. 

Do upvote our blogs if you find them helpful and engaging!

Until then, Keep Learning and Keep Coding!!


Keep Coding

Previous article
Merge K Sorted Arrays
Next article
K-th Smallest Element in the Unsorted Array using a Priority Queue
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass