Явный дублированный упорядоченный список по частоте

Question

Есть ли реализация дубликатов «списка» с порядком по частоте?

Например:

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

Это сложно с основной JDK, а не выполнимо с чистым Set, но если сторонние библиотеки справедливой игры, вы можете использовать Guava'sMultiset. Метод Multisets.copyHighestCountFirst сортирует заданный мультимножество по количеству вхождений каждого элемента.

Answer 2

Я не думаю, что есть стандартный класс библиотеки, который мог бы эффективно поддерживать такую ​​функциональность. Лучшая реализация зависит от того, как часто вы хотите использовать какие операции (добавлять, удалять, находить максимум, удалять максимум, перемещаться в порядке, ...).

---

Один специальный случай был бы, если бы вы только добавлять и удалять элементы и только время от времени вы хотели бы пройти/список всех элементов в порядке, в таком случае, я предлагаю следующие реализации:

Чтобы добавить и удалить, сохраните свои данные в любом Map<String, Integer> (например, HashMap или TreeMap), где имя соответствует частоте, что позволит быстро добавлять и удалять. Если вам нужно будет перечислять имена по частоте, просто потяните все данные на List и отсортируйте их с помощью подходящего компаратора.

---

Однако предыдущая реализация не удалась, если вы хотите, например, заглянуть в максимальный элемент после каждой вставки. В таком случае я бы использовал некоторую гибридную структуру, например, комбинацию карты и кучи (используйте оба), карту для быстрого поиска имен и кучи для выбора элемента с максимальной частотой.