how can print heap again and again?
after reading a input need to modify the heap and print for each input?? how?
How can print heap again and again?
You can do this question without using heap .
Refer this https://www.geeksforgeeks.org/find-top-k-or-most-frequent-numbers-in-a-stream/
For heap based approach,
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 how can i print heap again and again for each input??
please check sample test case.
after reading a input print heap and again read then print ,…so on…
For every element in the stream increase its frequency and store it in the last position of top vector. We can use hashing for efficiently fetching frequency of an element and increasing it.
Now find the position of element in top vector and iterate from that position to zero. For finding position we can make use of the find() function in C++ STL, it returns an iterator pointing to element if found in the vector.
And make that list of k+1 numbers sorted according to frequency and their value.
Print top k elements form top vector.
In this you only have to empty the heap once…only at the end when you have to print the result.
you can refer to this approach here
public List topKFrequent(int[] nums, int k) {
// build hash map : character and how often it appears
HashMap count = new HashMap();
for (int n: nums) {
count.put(n, count.getOrDefault(n, 0) + 1);
}
// init heap 'the less frequent element first'
PriorityQueue heap =
new PriorityQueue((n1, n2) -> count.get(n1) - count.get(n2));
// keep k top frequent elements in the heap
for (int n: count.keySet()) {
heap.add(n);
if (heap.size() > k)
heap.poll();
}
// build output list
List top_k = new LinkedList();
while (!heap.isEmpty())
top_k.add(heap.poll());
Collections.reverse(top_k);
return top_k;
}
I am not able to understand c++ , please explain in Java
not passing sample test case,
and please explain this line (n1, n2) -> count.get(n1) - count.get(n2));
how this code print after each input ???
please check sample test case , we need to print after every time of input, not only once.
@Vipin_coder
That is the syntax for lambda functions. I suggest you to read about lambda expressions in Java as they are extremenly useful for writing shorter codes with Java STL.
@Vipin_coder
This code does not print in itself but rather returns a Linked List node. This linked list can be traversed and each of its node values can be printed to obtain the desired output.
but above explanation is in cpp. vector and c++ stl n all
if i will direct print the head.poll instead of making linkedlist, it will work??
it will return for every input ??? please check sample test case ,output of this code is not matching with desired output
//please check this code is correct or not?
import java.util.*;
public class Main {
public static List topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> count = new HashMap<>();
for (int n: nums) {
int nval=(int)count.getOrDefault(n, 0);
count.put(n, (nval+1));
}
PriorityQueue<Integer> heap =
new PriorityQueue<>((n1, n2) -> count.get(n1) - count.get(n2));
for (int n: count.keySet()) {
heap.add(n);
if (heap.size() > k)
heap.poll();
}
List<Integer> top_k = new LinkedList<>();
while (!heap.isEmpty())
top_k.add(heap.poll());
Collections.reverse(top_k);
return top_k;
}
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
int k=sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
List<Integer> list= topKFrequent(arr,k);
for(int i=0;i<list.size();i++){
System.out.print(list.get(i)+" ");
}
System.out.println();
}
}
}@Vipin_coder
Vector in C++ is same as ArrayList in Java. You can even use a simple array in its place. Your choice entirely.
The code Abha shared is not the entire code. She just shared a snippet to give you an idea how to print the elements of the heap. However there are some more changes required as this code could fail in some testcases. The lambda function in this code only accounts for the frequency of the elements but not for the actual value itself. That is, in case of equal frequency, we must compare the values themselves. The lambda function does not account for that and hence must be ammended.
Also, the function is expected to get called multiple times after each input is taken. You have only called it once after taking the entire input.