Find the values corresponding to k-large elements

Question

My question is regarding data from a large file.

I have a huge file which is in this format - Primary_key Value( Eg: 10000001 1 10000002 5 10000009 200 etc. I want to find the values corresponding to the k - large elements in the primary_key column. For ex: If k=2, it should output 200 and 5 as per above example.

As it is a very large file, I was planning on using min heap method and I understand that pretty well. However, my data is in a key-value pair and I don't know how I can use that in the min heap sorting.

Any suggestions on how I can achieve this. Greatly appreciate any help on this.

Answer 1

yes your approach is right, you can use priority queue(with min heap) to achieve this. you can store your data in a map, then use it in priority queue like below.

PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((a, b) -> a.getValue()-b.getValue());
//psuedo code
for (line in file)
{ 
    //line[0] - denotes key and line[1] - denotes value
    count = map.getOrDefault(line[0], 0);
    map.put(num, count+line[1]);
}
for(Map.Entry<Integer, Integer> entry : counterMap.entrySet()) {
    pq.offer(entry);
    if(pq.size() > k) 
     pq.poll();
}

List<Integer> res = new LinkedList<>();
while(!pq.isEmpty()) {
    res.add(0, pq.poll().getValue());
}
return res;