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:
- Max-heap: In the max heap, the data present at the parent node must be greater than it’s children node.
- Min-heap: 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 min-heap)
Algorithm used:
We will use a min-heap in this implementation. Build a min heap of only size k.
- If the min-heap size is not k, push the element in min-heap.
- else compare the next coming element with the top of min-heap.
- If the element is greater than the top of min-heap, pop an element from min-heap(which will be eventually the top of min heap i.e the smallest in the heap). And push that element in min-heap.
- 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 Min-heap: 13
n=23 Min-heap: 13 23
n=45 Min-heap: 13 23 45
n=87 Min-heap: 13 23 45 87
n=-2 Min-heap: -2 13 23 45 87
n=3 Min-heap: 3 13 23 45 87 (It checks the top which is -2 and since it is less than n, it replaces it.)
n=94 Min-heap: 13 23 45 87 94 (It checks the top which is 3 and since it is less than n, it replaces it.)
n=4 Min-heap: 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