Heap: Top K Frequent Words

Problem Statement:

You are given an array of repeated numbers and a integer K.
You need to find the top K numbers that are repeated maximum frequency.

Example

Input:
arr[] = {3, 1, 4, 4, 5, 2, 6, 1},
k = 2

Output: 4 1

Solution

This solution is very simple.
We will use HashMap with Max Heap.

We will store the element and frequency pair in a HashMap.

Then we use a priority queue to store the frequency pair as Max-Heap.

Then we pop the PQ k times to get the result.

Solution in C++

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

using namespace std;


struct compare {
    bool operator()(pair<int, int> p1, pair<int, int> p2)
    {
        //if both frequency are same, then highest number should come first.
        if (p1.second == p2.second)
            return p1.first < p2.first;

        // insert element in decreasing order of frequency.
        return p1.second < p2.second;
    }
};
 
void print_N_mostFrequentNumber(int arr[], int n, int k)
{

    unordered_map<int, int> um;
    for (int i = 0; i < n; i++)
        um[arr[i]]++;

    priority_queue<pair<int, int>, vector<pair<int, int> >, compare> pq(um.begin(), um.end());
 
    cout <<"The numbers with most occurrences are:\n";
    for (int i = 1; i <= k; i++) {
        cout << pq.top().first << " ";
        pq.pop();
    }
}
 
int main()
{
    int arr[] = { 3, 1, 4, 4, 5, 2, 6, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    print_N_mostFrequentNumber(arr, n, k);
 
}

Output:

The numbers with most occurrences are:
4 1