Java non-duplicate ordered list by frequency

Question

Is there a non-duplicate "list" implementation with order by frequency?

For instance :

TreeSet<String> cities = new TreeSet<String>();

cities.add("NYC");    // Ordered list is [NYC]
cities.add("Boston"); // Ordered list is [Boston, NYC] (alphabetical order)
cities.add("NYC");    // Ordered list is [NYC, Boston] because NYC was added twice
cities.add("Philly"); 
cities.add("Philly");
cities.add("Philly"); // Ordered list is now [Philly, NYC, Boston] 

Answer 1

This is tricky with the basic JDK, and not doable with a pure Set, but if third-party libraries are fair game, you might use Guava's Multiset. The method Multisets.copyHighestCountFirst sorts a given multiset by the number of occurrences of each element.

Answer 2

I don't think there is any standard library class that could effectively support such functionality. Best implementation depends on how often you want to use which operations (add, remove, find maximum, remove maximum, traverse in-order, ...).

---

One special case would be if you would only add and remove elements and only from time to time you would want to traverse/list all elements in order, in such case, i suggest following implementation:

For adding and removing, store your data in any Map<String, Integer> (e.g. HashMap or TreeMap) where name maps to frequency, that will allow for fast adding and removing. If you will need to list names by frequency, just pull all data to an List and sort with suitable comparator.

---

However, the previous implementation fails terribly if you want to for example peek the maximum element after each insertion. In such case, I would use some hybrid structure, for example combine map and heap (use both), map for fast name lookup and heap for selecting element with maximum frequency.