Modo efficiente per trovare il valore minimo in Mappa

Question

Sto cercando di trovare key con il valore minimo in Map mostrato di seguito.

Map<Node, Integer> freeMap = new TreeMap<>(); 
Node minNode = null; 
     for (Map.Entry<Node, Integer> entry : freeMap.entrySet()) { 
      if (minNode == null) { 
       minNode = entry.getKey(); 
      } else { 
       if (entry.getValue() < freeMap.get(minNode)) { 
        minNode = entry.getKey(); 
       } 
      } 
     } 

In primo luogo, C'è un modo dritto in avanti per trovare key con il minimo value rispetto all'utilizzo foreach ciclo. In secondo luogo, puoi suggerire un approccio alternativo alla struttura dei dati che può essere utilizzato per memorizzare un oggetto Node e un valore Integer associato, in modo da poter recuperare entry con un valore minimo in tempo costante O (1).

Answer 1

struttura dati per O (1) Min Per una struttura di dati alternativo, come circa un Priority Queue.

È possibile utilizzare uno Comparator personalizzato o il tipo di dati implementare Comparable.

Dal javadoc:

Attuazione nota: questa implementazione fornisce O (log (n)) per i metodi Enqueing e dequeing (offerta, sondaggio, remove() e aggiungere); tempo lineare per i metodi remove (Object) e contiene (Object); e tempo costante per i metodi di recupero (sbirciatina, elemento e dimensione).

struttura dati per O (1) Min e ammortizzato O (1) trovare

Se si desidera sia min efficace ed efficiente ritrovamento e di controllare l'accesso alla struttura dei dati (altrimenti qual è il punto della domanda?) puoi semplicemente implementare la tua estendendo l'HashMap di Java per tenere traccia dell'elemento minimo.

È necessario eseguire l'override dei metodi put, putAll e remove. In ogni caso, puoi semplicemente chiamare il metodo super-classe (ad esempio super.put(key, value)) e quindi aggiornare l'elemento minimo, che viene mantenuto come membro di istanza della classe appena definita.

Si noti che questo aumenta il tempo di rimozione a (O (N)) (poiché è necessario aggiornare il valore minimo).

Answer 2

Sospetto che i valori di Integer non siano univoci nel sistema.

In questo caso, suggerisco di utilizzare TreeMultimap dalla libreria guava e utilizzare il valore Integer come chiave.

TreeMultimap<Integer, Node> freeMap = new TreeMultimap<>(); 
Node minNode = 
    freeMap.isEmpty() 
    ? null 
    : freeMap.entries().iterator().next().getValue(); 

Answer 3

miglioramento Minore non un intero gruppo:

Map<Node, Integer> freeMap = new TreeMap<Node, Integer>(); 
Node minNode = freeMap.isEmpty() ? null : (Node) freeMap.entrySet().iterator().next(); 
for (Map.Entry<Node, Integer> entry : freeMap.entrySet()) { 
    if (entry.getValue() < freeMap.get(minNode)) { 
     minNode = entry.getKey(); 
    } 
} 

Got the se il controllo fuori dal giro.

Answer 4

Se il vostro obiettivo è quello di migliorare tempo complessità, non c'è davvero un solo cambiamento possibile, da O (n log n) a O (n):

Map<Node, Integer> freeMap = new TreeMap<>(); 
Map.Entry<Node, Integer> minEntry = null; 
for (Map.Entry<Node, Integer> entry : freeMap.entrySet()) { 
    if (minEntry == null || entry.getValue() < minEntry.getValue()) { 
     minEntry = entry; 
    } 
} 
Node minNode = minEntry.getKey();