1

According to this question I have ordered a Java Map, as follows:

ValueComparator bvc =  new ValueComparator(originalMap);
Map<String,Integer> sortedMap = new TreeMap<String,Integer>(bvc);
sortedMap.putAll(originalMap);

Now, I would like to extract the K most relevant values from the map, in top-K fashion. Is there a highly efficient way of doing it without iterating through the map?

P.S., some similar questions (e.g., this) ask for a solution to the top-1 retrieval problem.

Community
  • 1
  • 1
Eleanore
  • 1,750
  • 3
  • 16
  • 33
  • 1
    I would strongly discourage you from using that implementation. Did you read the comments on the top answer? http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java#comment4699669_1283722 – Matt Ball Oct 28 '14 at 14:03
  • Ups, did not notice it. – Eleanore Oct 28 '14 at 14:12

1 Answers1

4

No, not if you use a Map. You'd have to iterate over it.

Have you considered using a PriorityQueue? It's Java's implementation of a heap. It has efficient operations for insertion of arbitrary elements and for removal of the "minimum". You might think about doing this here. Instead of a Map, you could put them into a PriorityQueue ordered by relevance, with the most relevant as the root. Then, to extract the K most relevant, you'd just pop K elements from the PriorityQueue.

If you need the map-like property (mapping from String to Integer), then you could write a class that internally keeps everything in both a PriorityQueue and a HashMap. When you insert, you insert into both; when you remove the minimal element, you pop from the PriorityQueue, and that then tells you which element you also need to remove from your HashMap. This will still give you log-time inserts and min-removals.

chiastic-security
  • 20,430
  • 4
  • 39
  • 67
  • Unfortunately, I need to keep two values (a String and an Integer) in the map. I need them both. I thought about putting in a Queue an Entry, but in this case the operation queue.contains() is difficult to be implemented – Eleanore Oct 28 '14 at 14:18
  • @Eleanore I've added something to the question about this. – chiastic-security Oct 28 '14 at 14:25