Heap: Top K Frequent Elements

Problem Statement:

You are given an integer array and a value k, you need to return the k most frequest elements.

Example

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Here both 1 and 2 repeated 2 or more times.

Solution

Here they have asked top or largest or greatest, then we have to use min_heap.

If they asked smalles, lowest, closest, then we need to use max_heap.

So in our question has asked to get top, so we need to use min_heap.

In the previous question, we sorted based on difference.

In this question, we need to sort based on frequency.

So to store the number and frequency, we need to use HashMap.

For our example, below is the number and frequency pair.

1  -> 3
2  -> 2
3  -> 1

We will use the element as key and frequency as pair in hashmap.

Then we need to sort based on frequency.

Pass 1: 1 -> 3

Heap: {3, 1}

Pass 2: 2 -> 2

Heap: {3, 1} {2, 2}

Pass 3: 3 -> 1

Heap: {3, 1} {2, 2} {1, 3}

Now the size is greater than “k”. So pop the top element.

The elements present inside the heap is our required answer.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 
#include <queue> 

using namespace std;

typedef pair<int, int> my_pair;

void print_top_k_frequent_nums(std::vector<int> &arr, int k)
{
  int n = arr.size();

  // create map for [element,frequency]
  unordered_map<int, int> mp; 
  for(auto i: arr)
  {
    mp[i]++;
  }


  //create min_heap
  priority_queue<my_pair, vector<my_pair>, greater<my_pair> >min_heap;
  for(auto i: mp)
  {
    min_heap.push(make_pair(i.second, i.first));
    
    if(min_heap.size() > k)
      min_heap.pop();
  }

  cout<<"Result = ";
  while(!min_heap.empty())
  {
    cout<<min_heap.top().second<<" ";
    min_heap.pop();
  }
  cout<<endl;

}

int main()
{
    vector<int> vec = { 1,1,1,3,2,2,4 };
 
    int k = 2;
 
    print_top_k_frequent_nums(vec, k);
 
    return 0;
}

Output:

Result = 2 1