K most frequent elements

#1

Can you also discuss how can this problem be implemented using priority queues ?

#2

Algorithm

  1. Create a Hashmap hm , to store key-value pair, i.e. element-frequency pair.
  2. Traverse the array from start to end.
  3. For every element in the array update hm[array[i]]++
  4. Store the element-frequency pair in a Priority Queue and create the Priority Queue, this takes O(n) time.
  5. Run a loop k times, and in each iteration remove the top of the priority queue and print the element.

i hope this helps
if yes hit a like and don’t forgot to mark doubt as resolved
if you have more doubts regarding this feel free to ask

1 Like
#3

how will the top of the priority queue be containing greatest value (frquencies) each time and not the key. ? Like do we need a comparison fn too ?

#4 

class compare { 
public: 
    bool operator()(pair<int, int> p1, pair<int, int> p2) 
    { 
        // if frequencies of two elemestructnts are same 
        // then the larger number should come first 
        if (p1.second == p2.second) 
            return p1.first < p2.first; 
  
        // insert elements in the priority queue on the basis of 
        // decreasing order of frequencies 
        return p1.second < p2.second; 
    } 
};

use this comparator

1 Like
#5

map<int,int>m;
for(i=0;i<n;i++)
m[a[i]]++;

vector<pair<int,int>>freqv(m.begin(),m.end());

i m not being able to create prioity queue after this. please help

#6

priority_queue<int,vector, CustomCompare > pq;