Effiziente Weise, Min-Wert in Karte zu finden

Question

Ich versuche, key mit Mindestwert in Map unten gezeigten zu finden.

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(); 
       } 
      } 
     } 

Erstens gibt es ein straight forward Weg key mit mindestens value als die Verwendung von foreach Schleife zu finden. Zweitens, können Sie einen alternativen Datenstrukturansatz vorschlagen, der zum Speichern eines Node Objekts und eines zugehörigen Integer Werts verwendet werden kann, sodass ich entry mit dem Minimalwert in der konstanten Zeit O (1) abrufen kann.

Answer 1

Datenstruktur für O (1) Min Für eine alternative Datenstruktur, wie etwa ein Priority Queue.

Sie können entweder eine benutzerdefinierte Comparator verwenden oder Ihren Datentyp implementieren Comparable.

Vom javadoc:

Implementierung Hinweis: Diese Implementierung stellt O (log (n)) Zeit für die Enqueing und dequeing Methoden (Angebot, Umfrage, remove() und fügen); lineare Zeit für das Entfernen (Objekt) und enthält (Objekt) Methoden; und konstante Zeit für die Abrufmethoden (Peek, Element und Größe).

Datenstruktur für O (1) Min und amortisiert O (1) finden

Wenn Sie sowohl effizient min und effizient finden wollen und Sie den Zugriff auf die Datenstruktur steuern (sonst was ist der Punkt der Frage?) Sie können einfach Ihre eigenen ausrollen, indem Sie Java's HashMap erweitern, um das Mindestelement zu verfolgen.

Sie müssen die Methoden put, putAll und remove außer Kraft setzen. In jedem Fall können Sie einfach die Superklassenmethode (z. B. super.put(key, value)) aufrufen und dann das minimale Element aktualisieren, das als Instanzenmitglied Ihrer neu definierten Klasse beibehalten wird.

Beachten Sie, dass diese die Entfernungszeit auf (0 (N)) erhöht (da Sie den Mindestwert aktualisieren müssen).

Answer 2

Ich vermute, dass Integer Werte in Ihrem System nicht eindeutig sind.

Wenn dies der Fall ist, schlage ich vor, verwenden Sie TreeMultimap von Guava-Bibliothek, und verwenden Sie Integer Wert als Schlüssel.

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

Answer 3

Minor Verbesserung nicht eine ganze Menge:

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(); 
    } 
} 

Haben Sie das, wenn Scheck aus der Schleife.

Answer 4

Wenn Ihr Ziel Zeit Komplexität zu verbessern, gibt es wirklich nur eine mögliche Änderung, von O (n log n) bis 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();