Top most frequent element using heap

#1

Given an array of n numbers. Your task is to read numbers from the array and keep at-most K numbers at the top (according to their decreasing frequency) every time a new number is read. We basically need to print top k numbers sorted by frequency when input stream has included k distinct elements, else need to print all distinct elements sorted by frequency. If frequency of two numbers are same then print them in increasing order. can’t understand this statement can you give some hint.

#2

Hey @shrutikatyal let me explain you this question with an approach, initialise a k priority queue swindow that store top k frequent number.
Whenever we gets a new number we will updated its frequency and then check it if that can be a part of our window or not.
We will find the element which has least frequncy . if this frequency is less than our current element frequency’ then we will remove that least frequent element and add then add our current element in our window.

#3

Though this is a beautiful explanation with dry run too, would suggest you to see this if any more doubts are left K frequency

#4

still don’t understand this statement .

#5

Which statement is creating trouble for you can you specify?

#6

For input:
n=5,k=2;
5 1 3 5 2

Explanation
So we first get 5 its freq is 1 and since its the only element we print it :5
Next we get 1 its freq is 1 but its smaller than 5 so it comes before it and since k is 2 we print : 1 5
Next we get 3 now all 1 ,3 ,5 have same freq and 1,3 comes first on order so we print :1 3
Next comes 5 now 5 freq is 2 and 1,3 freq is 1 so while printing we print : 5(most freq) 1(second most freq but smaller than others having same freq)
Next comes 2 its freq is 1 so again we print :5 1

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.