Очередная очередь с использованием 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");

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

Я думаю, что должен быть для цикла, и он должен быть итерацией через 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() (Предполагая, что вы знаете, что на карте есть хотя бы один элемент).

Видеть Документация TREEMULTIMAP Чтобы получить больше информации.

Answer 2

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

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

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

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

Answer 3

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

С помощью TREEMULTIMAP подход Jacobm предложил, следующий код более кратки.

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