Algorithmen & Datenstrukturen mit Java: Vorrang-Warteschlangen

Schnittstelle	für Vorrang-Warteschlangen: interface PriorityQueue
	package ds.interfaces; /** Simple interface for maps */ import java.util.Iterator; import ds.util.Invariant; import ds.util.Function2; import ds.util.P; // example class for priorities import ds.util.V; // example class for values import ds.util.PV; // priority-value pair public interface PriorityQueue extends Iterable<PV>, Invariant { boolean isEmpty(); int size(); PV findMin(); PriorityQueue insert(P p, V v); PriorityQueue removeMin(); PriorityQueue copy(); // inherited // public Iterator<PV> iterator(); // public inv(); }
Hilfsklassen	für die Prioritäten und Werte analog zu Schlüssel-Wert-Paaren
P	package ds.util; /** just an example class for comparable elements */ public class P implements Comparable<P> { public final int prio; public P(int p) { prio = p; } // smart constructor public static P mkP(int v) { return new P(v); } public int compareTo(P p2) { if (prio == p2.prio) return 0; if (prio > p2.prio) return 1; else return -1; } public boolean equalTo(P p2) { return compareTo(p2) == 0; } public String toString() { return "" + prio; } }
V	package ds.util; /** just an example class for elements without any specific properties */ public class V { public final int value; private V(int v) { value = v; } // smart constructor public static V mkV(int v) { return new V(v); } public String toString() { return "" + value; } }
PV	package ds.util; import ds.util.P; import ds.util.V; public final class PV { public final P fst; public final V snd; private PV(P p, V v) { fst = p; snd = v; } public String toString() { return "(" + fst.toString() + ", " + snd.toString() + ")"; } // smart constructor public static PV mkPair(P p, V v) { return new PV(p, v); } }

Ziele	für Vorrang-Warteschlangen
1.	Speicherung beliebig vieler Elemente (einfache Werte: Zahlen, ..., Priorität-Wert-Paare)
2.	Effizienter Zugriff auf das kleinste Element auf das Element mit der höchsten Priorität
3.	Effizientes Einfügen
4.	Effizientes Löschen des kleinsten Elements

?	Mögliche Lösungen
?	Laufzeit-Effizenz, Komplexitätsklassen
binäre Halde	Klassenstruktur
	public abstract class BinaryHeap implements PriorityQueue { ... private static final class Empty extends BinaryHeap { ... } private static final class Node extends BinaryHeap { final P p; // priority final V v final BinaryHeap l; final BinaryHeap r; ... } }
	Klassenstruktur wie bei binären Suchbäumen
	Die Schlüssel aus den Suchbäumen sind hier Priorotäten (vom Typ P) Zu einer Priorität sind mehrere Prioritäts-Wert-Paare zulässig

Invariante	für die binäre Halde
	Für alle Knoten gilt: Die Elemente (Prioritäten) in den Kindknoten sind nicht kleiner als das Element im Knoten selbst.

Konstruktor-Funktionen	wie bei binären Suchbäumen
	public static BinaryHeap empty() { return EMPTY; } public static BinaryHeap singleton(P p, V v) { return new Node(p, v, EMPTY, EMPTY); }

Implementierung	wird in der Vorlesung entwickelt