# 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