Package shortestPath

Class IndexMinPQ<Key,​PrioValue>

java.lang.Object
shortestPath.IndexMinPQ<Key,​PrioValue>
Type Parameters:
Key - Schlüsseltyp. Vorsicht: hashCode muss geeignet überschrieben sein.
PrioValue - Prioritätswerte. PrioValue muss vom Subtyp Comparable<PrioValue> sein (Prüfung zur Laufzeit).
public class IndexMinPQ<Key,​PrioValue> extends Object
Prioritätsliste mit Elementen bestehend aus Schlüssel und Prioritätswert. Liste ist geordnet nach den Prioritätswerten (Heap Struktur). Prioritätswerte können effizient in O(log n) geändert werden. Beachte Unterschied zur Java PriorityList, wo Prioritätswerte nur mit O(n) geändert werden können. Operation add, change, remove, removeMin in O(log n). Operation get, getMinKey, getMinValue in O(1) (Hashtabelle bzw. indizierter Zugriff). Siehe auch IndexMinPQ in Sedgewick, Algorthms, 4.ed., 2012, Seite 320.
Since:
20.12.2024

  • Constructor Details

    • IndexMinPQ

      public IndexMinPQ()
      Konstruktor.

  • Method Details

    • clear

      public final void clear()
      Löscht die Prioritätsliste.

    • size

      public int size()
      Liefert die Anzahl der Elemente in der Prioritätsliste zurück.
      Returns:
      Abzahl der Elemente.

    • isEmpty

      public boolean isEmpty()
      Prüft, ob die Prioritätsliste leer ist.
      Returns:
      true, falls die Prioritätsliste leer ist.

    • add

      public boolean add​(Key k, PrioValue v)
      Fügt Schlüssel und Prioritätswert ein.
      Parameters:
      k - Schlüssel
      v - Prioritätswert
      Returns:
      true, falls Schlüssel frisch eingefügt wurde.

    • change

      public PrioValue change​(Key k, PrioValue v)
      Ändert den Prioritätswert für Schlüssel k.
      Parameters:
      k - Schlüssel
      v - neuer Prioritätswert
      Returns:
      alter Prioritätswert oder null, falls Schlüssel k nicht vorhanden ist.

    • get

      public PrioValue get​(Key k)
      Gibt den Prioritätswert für Schlüssel k zurück.
      Parameters:
      k - Schlüssel.
      Returns:
      Prioritätswert oder null, falls Schlüssel k nicht vorhanden ist.

    • remove

      public PrioValue remove​(Key k)
      Löscht Schlüssel und Prioritätswert.
      Parameters:
      k - Schlüssel.
      Returns:
      Alter Prioritätswert oder null, falls Schlüssel k nicht vorhanden ist.

    • removeMin

      public Key removeMin()
      Löscht kleinsten Prioritätswert mit Schlüssel.
      Returns:
      Gelöschter Schlüssel oder null, falls Prioritätsliste leer ist.

    • getMinKey

      public Key getMinKey()
      Liefert Schlüssel mit kleinstem Prioritätswert.
      Returns:
      Schlüssel mit kleinstem Prioritätswert oder null, falls Prioritätsliste leer ist.

    • getMinValue

      public PrioValue getMinValue()
      Liefert kleinsten Prioritätswert.
      Returns:
      kleinster Prioritätswert oder null, falls Prioritätsliste leer ist.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • main

      public static void main​(String[] args)
      Parameters:
      args - the command line arguments