Каков наилучший способ получить верхние N элементов в Map <String, Double> на основе их значений?

Question

Например, если у меня карта состоит из {"A", 0.0}, {"B", 3.14}, {"C", 3.14}, {"D", 8.8}, {"E", 2.1}, {"F", 1.01}, а верхние 3 клавиши будут {"D", "B", "C"}.

Мне известен процедурный способ сделать это, но есть ли более умный / функциональный способ сделать это в Java 8?

Редактировать: обратите внимание, что мы можем поместить каждый элемент карты в приоритетную очередь размера N, поэтому временная сложность должна составлять M log (N), быстрее, чем сортировка всех M элементов, которая равна M журнал (M).

Редактировать 2: По запросу, это то, что у меня есть:

 public static void main(String args[]) {
    final Map<String, Double> map = new HashMap<String, Double>() {{
      put("A", 0.0);
      put("B", 3.14);
      put("C", 3.14);
      put("D", 8.8);
      put("E", 2.1);
      put("F", 1.01);
    }};
    System.out.println("answer= " + getTopN(map, 3).toString());
  }

  static List<String> getTopN(final Map<String, Double> map, int n) {
    // Creating priority queue with limit size n
    PriorityQueue<Entry<String, Double>> pq = new PriorityQueue<>(n, Entry.comparingByValue());
    for (Entry<String, Double> entry : map.entrySet()) {
      pq.add(entry);
      if (pq.size() > n) {
        pq.poll();
      }
    }
    Stack<String> stack = new Stack<>();
    while (!pq.isEmpty()) {
      stack.add(pq.poll().getKey());
    }
    final ArrayList<String> answer = new ArrayList<>();
    while (!stack.isEmpty() && n-- > 0) {
      answer.add(stack.pop());
    }
    return answer;
  }

Answer 1

Ваш код можно улучшить, используя TreeSet (вместо PriorityQueue и Stack):

static List<String> getTopN(Map<String, Double> map, int n) {

    TreeSet<Map.Entry<String, Double>> topN = new TreeSet<>(
        Map.Entry.<String, Double>comparingByValue()
            .reversed()                         // by value descending, then by key
            .thenComparing(Map.Entry::getKey)); // to allow entries with repeated values

    map.entrySet().forEach(e -> {
      topN.add(e);
      if (topN.size() > n) topN.pollLast();
    });

    return topN.stream()
        .map(Map.Entry::getKey)
        .collect(Collectors.toList());
}

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

Метод TreeSet.pollLast() является эквивалентом метода PriorityQueue.poll().

Answer 2

Вот способ, который использует обратный двойной компаратор по значению записи:

Map<String, Double> map = new HashMap<>();
map.put("A", 0.0);
map.put("B", 3.14);
map.put("C", 3.14);
map.put("D", 8.8);
map.put("E", 2.1);
map.put("F", 1.01);

List<String> topKeys = map.entrySet().stream()
        .sorted(Comparator.<Entry<String, Double>>comparingDouble(Entry::getValue)
                 .reversed())
        .limit(3) //limit to 3
        .map(Entry::getKey)
        .collect(Collectors.toList());

Возвращенный список содержит [D, B, C]