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

1. Max-heap: In the max heap, the data present at the parent node must be greater than it’s children node.
2. 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.

1. If the min-heap size is not k, push the element in min-heap.
2. 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```
1. `n=13   Min-heap: 13`
2. `n=23  Min-heap: 13 23`
3. `n=45   Min-heap: 13 23 45`
4. `n=87   Min-heap: 13 23 45 87`
5. `n=-2   Min-heap: -2 13 23 45 87`
6. `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.)`
7. `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.)`
8. `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.)`
9. `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++