CODEWITHSUNDEEP
javafunctional-programming
ijklr
ijklr

Reputation: 181

What's the best way to get top N elements in a Map<String, Double> based on their values?

For example, if I have a map consists of {"A", 0.0}, {"B", 3.14}, {"C", 3.14}, {"D", 8.8}, {"E", 2.1}, {"F", 1.01} and the top 3 keys would be {"D", "B", "C"}.

I know the procedural way to do this but is there a smarter/functional way to do it in Java 8?

Edit: note that we can put each element of the map into a priority queue of size N, so the time complexity should be Mlog(N), faster than sorting all M elements which is Mlog(M).

Edit 2: As requested, this is what I've got:

 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;
  }

Upvotes: 2

Views: 1467

Answers (2)

fps
fps

Reputation: 34460

Your code can be improved by making use of TreeSet (instead of PriorityQueue and 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());
}

Note that I'm using a comparator that sorts the TreeSet of entries by value in descending order and then by key. This is to make it possible for the set to contain entries with equal values.

The TreeSet.pollLast() method is the equivalent of PriorityQueue.poll() method.

Upvotes: 1

ernest_k
ernest_k

Reputation: 45329

Here's a way that uses a reverse Double comparator by entry value:

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());

The returned list contains [D, B, C]

Upvotes: 3

Related Questions