Skip to main content
Java

PriorityQueue, HashMap und Sortierung

 

Frage: Wenn ich ein Objekt aus der Map hole und bearbeite, ist es dann automatisch in der PriorityQueue sortiert?

Antwort: NEIN. Auf gar keinen Fall.

Das Problem

Die PriorityQueue (ein binärer Heap) sortiert die Elemente nur zu zwei Zeitpunkten:

  1. Beim Hineinlegen (offer/add): Das Element „blubbert“ an die richtige Stelle (Sift Up).

  2. Beim Herausnehmen des Kleinsten (poll): Das letzte Element wird nach oben geholt und „sickert“ nach unten (Sift Down).

Die Queue überwacht deine Objekte nicht. Wenn du ein Objekt veränderst, das bereits in der Queue liegt, veränderst du dessen „Gewicht“, aber es bleibt an der alten Position liegen.

Folge: Die Sortierung ist kaputt (Heap Corruption). Das nächste poll() liefert vielleicht nicht mehr das kleinste Element, oder schlimmer: Die Queue verhält sich unvorhersehbar.

Wie löst man das?

Du musst die Sortierung manuell anstoßen. Da es in der Java-Standard PriorityQueue keine update()-Methode gibt, ist der Weg:

  1. Entfernen (mit dem alten Wert).

  2. Ändern (neuen Wert setzen).

  3. Hinzufügen (neu einsortieren).

Java

MeinObjekt obj = myHashMap.get(id);

// 1. WICHTIG: Erst aus der Queue entfernen!
// Achtung: Das ist teuer (siehe unten)
priorityQueue.remove(obj); 

// 2. Wert ändern
obj.setPriority(neuePrioritaet);

// 3. Neu einfügen (jetzt wird sortiert)
priorityQueue.add(obj);

Performance-Analyse (Big O Notation)

Hier liegt der Hund begraben:

  • PriorityQueue.add(): O(log n) (Sehr schnell)

  • PriorityQueue.poll(): O(log n) (Sehr schnell)

  • PriorityQueue.remove(Object): O(n) (Langsam!)

Da die PriorityQueue nicht weiß, wo genau das Objekt im Heap liegt (außer es ist zufällig ganz oben), muss sie intern das interne Array durchsuchen, um es zu finden und zu löschen. Wenn du viele Elemente hast, wird das Ändern von Prioritäten extrem langsam.

Die bessere Datenstruktur für „Update Priority“

Wenn du häufig Prioritäten ändern musst (wie beim Dijkstra-Algorithmus oder A*), ist die Standard-Java PriorityQueue schlecht.

Alternativen:

  1. TreeSet:

    • Sortiert immer automatisch beim Einfügen.

    • Auch hier gilt: remove() -> modify -> add().

    • Vorteil: remove() ist hier O(log n), also viel schneller als bei der PriorityQueue.

    • Nachteil: Braucht etwas mehr Speicher und ist bei reinem add/poll etwas langsamer als PQ.

  2. Lazy Deletion (Faules Löschen) – oft der beste Hack:Du löschst das Objekt gar nicht aus der Queue.

    • Du änderst das Objekt in der HashMap.

    • Du fügst das Objekt nochmal in die PriorityQueue ein (mit dem neuen Wert).

    • Jetzt ist das Objekt zweimal drin (einmal „alt/falsch“, einmal „neu/richtig“).

    • Beim poll() prüfst du: „Ist dieses Objekt das aktuelle aus der Map?“. Wenn nein (es ist eine alte „Geister-Version“), wirfst du es weg und nimmst das nächste.

Zusammenfassung:

  • Für Timer: Nimm ein long expirationTime Feld direkt im Objekt. Schnellste und sauberste Lösung.

  • Für PriorityQueue: Du musst rausnehmen und neu einfügen. Wenn das oft passiert, nutze lieber ein TreeSet oder die „Lazy Deletion“ Strategie, um die O(n)-Suche beim Löschen zu vermeiden.

Leave a Reply