Priorità coda utilizzando MultiMap - Java

Question

Devo implementare priorità coda utilizzando MultiMap. Io uso MultiMap da Google collezioni. Il codice seguente crea un MultiMap e aggiunge alcuni elementi in esso.

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

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

Ora il mio problema è come scrivere il metodo pop?

Penso che ci dovrebbe essere un ciclo e dovrebbe essere scorrendo MultiMap.

Il tasto più basso dovrebbe essere la massima priorità, quindi in C ++ vorrei impostare un puntatore al primo elemento e incrementarlo. Come fare in Java?

Answer 1

Il HashMultimap stai usando non ti darà alcun aiuto nella scelta in modo efficiente l'elemento più basso. Invece utilizzare un TreeMultimap (anche in Google Collections) che consente di specificare un ordinamento e iterare attraverso gli elementi della lista in questo ordine. Per esempio:

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

Si noterà che viene stampato sempre fuori le voci in ordine di priorità, in modo da ottenere il primo elemento di priorità si può solo fare multimap.entries().iterator().next() (supponendo che si sa la mappa ha almeno un elemento).

la documentazione TreeMultimap per ulteriori informazioni.

Answer 2

Se ho la comprensione correttamente che si sta utilizzando Multimap come i meccanismi interni per la propria classe CodaConPriorita, piuttosto che cercare di usare Multimap come una coda di priorità, allora probabilmente si dovrebbe tenere un SortedSet (lo chiamerò sortedKeys ) di tutte le chiavi. Quindi è possibile utilizzare multimap.get(sortedKeys.first()) al pop il primo elemento.

Per "tenere un SortedSet", voglio dire che ogni volta che si aggiunge qualcosa al tuo Multimap, aggiungere la sua chiave per una SortedSet. Quando si rimuove elementi dal Multimap, togliere le chiavi dal SortedSet. L'obiettivo è che i vostri soggiorni SortedSet uguali a Multimap.keySet (), ma senza il sovraccarico di chiamare SortedSet.clear(); SortedSet.addAll(...) tutto il tempo.

L'alternativa sta per essere la creazione di un SortedSet ogni volta che sarebbe molto più lento. Può aiutare a capire quello che sto dicendo però:

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

Answer 3

Potresti semplicemente utilizzare il CodaConPriorita classe nel JDK?

Con l'approccio jacobm TreeMultimap suggerito, il seguente codice è più conciso.

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