查找与 k 大元素对应的值

Question

我的问题是关于大文件中的数据。

我有一个这种格式的大文件 - Primary_key Value( 例如：10000001 1 10000002 5 10000009 200等 我想在primary_key列中找到与 k - 大元素对应的值。例如：如果 k=2，它应该按照上面的例子输出 200 和 5。

由于这是一个非常大的文件，我计划使用最小堆方法，我非常了解这一点。但是，我的数据在键值对中，我不知道如何在最小堆排序中使用它。

关于我如何实现这一目标的任何建议。非常感谢对此的任何帮助。

Answer 1

是的，您的方法是正确的，您可以使用优先级队列(带有最小堆(来实现此目的。 您可以将数据存储在地图中，然后在优先级队列中使用它，如下所示。

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;