Найти значения, соответствующие k-большим элементам

Question

Мой вопрос касается данных из большого файла.

У меня есть огромный файл в этом формате - значение Primary_key (например, 10000001 1 10000002 5 10000009 200 и т. Д. Я хочу найти значения, соответствующиек - большие элементы в столбце primary_key. Например: если k = 2, то должно вывести 200 и 5, как в примере выше.

Поскольку это очень большой файл, я планировал использовать minМетод кучи, и я понимаю это довольно хорошо. Однако мои данные находятся в паре ключ-значение, и я не знаю, как я могу использовать это в сортировке минимальной кучи.

Любые предложения о том, как я могу достичьЭто. Очень признателен за любую помощь в этом.

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;