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.

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++