I know how to do this question using hashmap but please guide me on how to do this question using heaps.
Top k most frequent in a stream of integers
@Kajal There are 2 ways by which you can solve this problem using heaps.
-
Using a MAX-HEAP (with no size limit): Build a max heap based on frequency count of integers. At the end, the top k elements of your max heap will be the k most frequent in the stream.
-
Using a MIN-Heap of size K (more efficient):Maintain a min heap of size k based on frequency count of integers.
Understand case 2 with an example:
Consider an array arr[] = {7, 10, 11, 5, 2, 5, 5, 7, 11, 8, 9,2},
k = 4
Maintain a freq count array:
7 with frequency 2, 10 with frequency 1,11 with freq 2, 5 with freq 3, 2 with freq 2, 8 with freq 1, 9 with freq 1.
Now push these in a min heap and ensure that its size is k(ie. 4 here):
So after pushing the first 4 elements in the min heap: 10 with frequency 1 will be at the top of the heap.
Now continuing further: We reach 2 with frequency 2
We check the size of the heap. The size of the heap has already reached its limit that is 4. So we now check another condition : If the frequency of the next element in stream is greater than the frequency of the top element in stream. We pop the top element of the heap and push the next element of stream into the heap.
So here (2 with frequency 2 > 10 with frequency 1) We pop 10 with frequency 1 from the heap and push 2 with frequency 2 into the heap.
Now continuing further, we reach 8 with frequency 1: Size of the heap is already 4. And 8 with frequency 1 is not greater than 2 with frequency 2( current top of heap). So we do nothing and move further.
Similarly for 9 with frequency 1, we do nothing and move further.
At the end, the elements of the min heap of size k will form your answer.
Hope this helps 
but we have to print the heap again and again…and we cant iterate over every element in a heap, so how will we give answer to queries while in the middle of the stream.
No… At the end, the elements of the min heap of size k will form your answer. You can only pop the top elements of the heap based on the above conditions i mentioned. After complete iteration of the frequency array. You are ready with a k sized heap. Pop elements of this k sized heap and this will form your answer.
Sample Input 1 5 2 5 1 3 5 2 Sample Output 5 1 5 1 3 5 1 5 1 Please explain your approach with reference to this sample input given in the question. Because I am not able to understand the fact that how to print the whole heap at any type 2 query without empitying out the whole heap.
Sorry, my bad. I mistook this to another question where there is no query type. I have explained you the approach for this question https://leetcode.com/problems/top-k-frequent-elements/ For such a case the above approach which i have explained will work. In this you only have to empty the heap once…only at the end when you have to print the result.
For your question, a very similar approach would be followed as i have explained earlier.Just one difference is there that you have to empty your heap at every iteration.Refer this implementation. I have commented some steps.
Dry run this code to understand well.
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.
Can you please explain why are you doing this step?
while(l1–)//Emptying the heap
pq.pop();
In line number 49 and 50