CODEWITHSUNDEEP
javaalgorithmdictionary
Jason
Jason

Reputation: 11363

Find top ten values in a Map

Say I have a TreeMap<String, Treeset<Song>>, where object Song has three String fields and an internal CompareTo method. The keys for the map are unique words in the lyrics that are not common words such as "she", "the", "if", or "on". There are multiple copies of Songs in the map, since there are an average of 60 words mapped to a single Song.

For extra credit, the professor asked us to come up with an algorithm to find the top 10 values in the map. I didn't solve the problem in time, which is why I'm asking here.

The part that I'm stumped on is, unlike with an ordered array or list, you can't just grab the top values sequentially. So, I thought about:

Create a PriorityQueue<Node> with the Comparator sorting the Nodes based
on the Set size

iterate over the map
   for each map node
     create a Node object with the key-value pair
     insert Node into the queue

Even though the PriorityQueue will end up with all the key-value pairs, the top sizes will be at the top, and I can just retrieve the first ten.

This seems like a very roundabout way, since this particular map has 31,000+ nodes mapping to over 637,000 values. Is there a better way?

Upvotes: 2

Views: 676

Answers (2)

Jason
Jason

Reputation: 11822

A simple modification of your algorithm:

Create a PriorityQueue<Node> with the Comparator sorting the Nodes based
on the Set size

iterate over the map
  for each map node
    if value for node is larger than last entry in priority queue
      create a Node object with the key-value pair
      insert Node into the queue
      trim the queue to ten entries

At completion, the priority queue will only contain the top 10 entries.

Upvotes: 1

piccolbo
piccolbo

Reputation: 1315

I am not sure you want the top 10 by key, in which case Soldier.moth is right and you can specifically obtain a descending view calling descendingMap and then iterate for the first 10 elements. But if you want the top 10 by some other relation, just iterate over the elementSet and store the current top 10 in a sorted data structure, like TreeSet specifying a comparator based on size -- not sure what size you mean but you probably know -- and for every element you replace the smallest of the 10 if it is smaller than the current. You obtain the smallest with firstKey

Upvotes: 0

Related Questions