Merge 3 arrays in sorted order in C++
In this tutorial, we will learn how to merge 3 arrays in sorted order in C++. Below is an interesting solution based on min-heap implemented by using a priority queue. For example-
Input:
3
-1 35 45
4
7 8 9 0
5
-23 -87 4 5 3
Output:
-87 -23 -1 0 3 4 5 7 8 9 35 45
How to merge 3 arrays in sorted order in C++
Basically, we will use a min-heap in our code. Heaps are a complete binary tree. In min-heap, the data present at the parent is less than it’s children node.
Push the elements of all the three arrays one by one in a min-heap. It gets stored in a tree-like this below:
We start printing from the top of min-heap and they get printed in sorted order.
Here, is the code implementation:
#include<bits/stdc++.h> using namespace std; int main() { int n1; cin>>n1; int a[100],b[100],c[100]; for(int i=0;i<n1;i++) { cin>>a[i]; } int n2; cin>>n2; for(int i=0;i<n2;i++) { cin>>b[i]; } int n3; cin>>n3; for(int i=0;i<n3;i++) { cin>>c[i]; } priority_queue<int,vector<int>,greater<int> > pq; for(int i=0;i<n1;i++) { pq.push(a[i]); } for(int i=0;i<n2;i++) { pq.push(b[i]); } for(int i=0;i<n3;i++) { pq.push(c[i]); } while(pq.empty()==false) { cout<<pq.top()<<" "; pq.pop(); } }
Here the Input is:
3
-1 35 45
4
7 8 9 0
5
-23 -87 4 5 3
And the Output is:
-87 -23 -1 0 3 4 5 7 8 9 35 45
Also, refer to:
Count the number of occurrences of an element in a linked list in C++
Time complexity: It will be o(m+n+k) where m,n, and k are sizes of the array as the arrays are only traversed once.
Leave a Reply