Приоритетная очередь с использованием MultiMap - Java

Question

Я должен реализовать очередь приоритетов с помощью MultiMap. Я использую MultiMap из Коллекций Google. Следующий код создает MultiMap и добавляет в него несколько элементов.

Multimap<Integer, String> multimap = HashMultimap.create(); 

    multimap.put(5,"example"); 
    multimap.put(1,"is"); 
    multimap.put(1,"this"); 
    multimap.put(4,"some"); 

Теперь моя проблема заключается в том, как написать метод pop?

Я думаю, что должен быть цикл for, и он должен повторяться через MultiMap.

Самый низкий ключ должен быть наивысшим приоритетом, поэтому в C++ я бы установил указатель на первый элемент и увеличил его. Как это сделать в Java?

Answer 1

HashMultimap вы используете не даст вам помощь в выборе эффективного нижнего элемента. Вместо этого используйте TreeMultimap (также в Google Collections), который позволяет вам указать порядок и выполнить итерацию элементов в списке в этом порядке. Например:

for (Map.Entry<Integer, String> entry : multimap.entries()) { 
    System.out.println("Item " + entry.getValue() + " has priority " + entry.getKey(); 
} 

Вы заметите, что это всегда выводит записи в порядке приоритета, так чтобы получить первый приоритетный элемент, который вы можете просто multimap.entries().iterator().next() (предполагая, что вы знаете, что карта имеет, по меньшей мере, один элемент).

Для получения дополнительной информации см. the TreeMultimap documentation.

Answer 2

Если я правильно понимаю, что вы используете Multimap как внутренние для собственного класса PriorityQueue, а не просто пытаетесь использовать Multimap в качестве очереди приоритетов, то вам, вероятно, следует сохранить SortedSet (я позвоню ему sortedKeys) всех ключей. Затем вы можете использовать multimap.get(sortedKeys.first()), чтобы заполнить первый элемент.

«Сохраняя SortedSet», я имею в виду, что каждый раз, когда вы добавляете что-то в свой Multimap, добавьте его ключ в SortedSet. Когда вы удаляете элементы из своего Multimap, удалите их ключи из SortedSet. Цель состоит в том, чтобы ваш SortedSet оставался равным Multimap.keySet(), но без накладных расходов на вызов SortedSet.clear(); SortedSet.addAll(...) все время.

Альтернативой будет создание SortedSet каждый раз, что будет намного медленнее. Это может помочь вам понять, что я говорю, хотя:

public Collection<V> pop() { 
    SortedSet keys = new TreeSet(multimap.keySet()); 
    return multimap.get(keys.first()); 
} 

Answer 3

Не могли бы вы просто использовать класс PriorityQueue в JDK?

Предлагаемый подход TreeMultimap, предложенный jacobm, более краткий.

Iterator<String> iterator = multimap.values().iterator(); 
String value = iterator.next(); 
iterator.remove();