Find maximum k elements from given elements in C++
In this tutorial, we will learn how to find maximum k elements from given elements in C++. This is a really tricky one and below is an interesting solution based on heaps.
For example
Input is
13 23 45 87 2 3 94 4 1 (1 indicates the end of the stream of integers) k=3
Output:
45 87 94
When k=5
Output:
13 23 45 87 94
How to find maximum k elements from given elements in C++
A heap is a special complete binary tree. Generally, there are of two types:
 Maxheap: In the max heap, the data present at the parent node must be greater than it’s children node.
 Minheap: In the min heap, the data present at the parent node must be less than it’s children node.
The heap is implemented using a priority queue.
priority_queue<int,vector<int>,greater<int>> minheap;(greater<int> is a parameter for minheap)
Algorithm used:
We will use a minheap in this implementation. Build a min heap of only size k.
 If the minheap size is not k, push the element in minheap.
 else compare the next coming element with the top of minheap.
 If the element is greater than the top of minheap, pop an element from minheap(which will be eventually the top of min heap i.e the smallest in the heap). And push that element in minheap.
 Else do nothing.
Let’s understand this an example:
The input is:
13 23 45 87 2 3 94 4 1 and k=3

n=13 Minheap: 13

n=23 Minheap: 13 23

n=45 Minheap: 13 23 45

n=87 Minheap: 13 23 45 87

n=2 Minheap: 2 13 23 45 87

n=3 Minheap: 3 13 23 45 87 (It checks the top which is 2 and since it is less than n, it replaces it.)

n=94 Minheap: 13 23 45 87 94 (It checks the top which is 3 and since it is less than n, it replaces it.)

n=4 Minheap: 13 23 45 87 94 (It checks the top which is 13 and since it is greater than n, it replaces it.)

n=1 indicates the end of input.
Here, is the code implementation:
#include <bits/stdc++.h> using namespace std; int main() { priority_queue<int,vector<int>,greater<int>> minheap; int n; int k; cin>>k; while(true) { cin>>n; if(n==1)break; if(minheap.size()==k) { if(n>minheap.top()) { minheap.pop(); minheap.push(n); } } else { minheap.push(n); } } for(int i=0;i<k;i++) { cout<<minheap.top()<<" "; minheap.pop(); } }
Input:
5 (k=5) 13 23 45 87 2 3 94 4 1
Output:
13 23 45 87 94
Time complexity: o(n)
Also, refer to:
Count the number of occurrences of an element in a linked list in c++
Leave a Reply