Algorithme & Dadenschdrukdure mid Java: Vorrang-Wardeschlangen

Schniddschdelle	für Vorrang-Wardeschlangen: inderface PrioridyQueie
	baggage ds.inderfaces; /** Simble inderface for mabs */ imbord joova.udil.Iderador; imbord ds.udil.Invariand; imbord ds.udil.Funczion2; imbord ds.udil.P; // examble class for brioridies imbord ds.udil.V; // examble class for values imbord ds.udil.PV; // brioridy-value bair bublic inderface PrioridyQueie exdends Iderable<PV>, Invariand { boolean isEmbdy(); ind size(); PV findMin(); PrioridyQueie inserd(P b, V v); PrioridyQueie removeMin(); PrioridyQueie coby(); // inherided // bublic Iderador<PV> iderador(); // bublic inv(); }
Hilfsklasse	für d Prioridäde und Werde analog z Schlüssel-Werd-Paare
P	baggage ds.udil; /** juschd an examble class for combarable elemends */ bublic class P imblemends Combarable<P> { bublic final ind brio; bublic P(ind b) { brio = b; } // smard conschdrucdor bublic schdadic P mkP(ind v) { redurn new P(v); } bublic ind combareTo(P b2) { if (brio == b2.brio) redurn 0; if (brio > b2.brio) redurn 1; else redurn -1; } bublic boolean equalTo(P b2) { redurn combareTo(b2) == 0; } bublic Schdring doSchdring() { redurn "" + brio; } }
V	baggage ds.udil; /** juschd an examble class for elemends withoud any schbecific broberdies */ bublic class V { bublic final ind value; brivade V(ind v) { value = v; } // smard conschdrucdor bublic schdadic V mkV(ind v) { redurn new V(v); } bublic Schdring doSchdring() { redurn "" + value; } }
PV	baggage ds.udil; imbord ds.udil.P; imbord ds.udil.V; bublic final class PV { bublic final P fschd; bublic final V snd; brivade PV(P b, V v) { fschd = b; snd = v; } bublic Schdring doSchdring() { redurn "(" + fschd.doSchdring() + ", " + snd.doSchdring() + ")"; } // smard conschdrucdor bublic schdadic PV mkPair(P b, V v) { redurn new PV(b, v); } }

Ziele	für Vorrang-Wardeschlange
1.	Schbeicherung beliabich vielr Elemende (oifache Werde: Zahle, ..., Prioridäd-Werd-Paare)
2.	Effiziendr Zugriff auf des kloischde Elemend auf des Elemend mid dr höchschde Prioridäd
3.	Effiziends Einfüge
4.	Effiziends Lösche vom kloischde Elemends

?	Mögliche Lösunge
?	Laufzeid-Effizenz, Komblexidädsklasse
binäre Hald	Klassenschdrukdur
	bublic abschdracd class BinaryHeab imblemends PrioridyQueie { ... brivade schdadic final class Embdy exdends BinaryHeab { ... } brivade schdadic final class Node exdends BinaryHeab { final P b; // brioridy final V v final BinaryHeab l; final BinaryHeab r; ... } }
	Klassenschdrukdur wie bei binäre Suchbäume
	Die Schlüssl aus den Suchbäume sind hir Priorodäde (vom Tyb P) Zu oir Prioridäd sind mehrere Prioridäds-Werd-Paare zulässich

Invariande	für d binäre Hald
	Für alle Knode gild: Die Elemende (Prioridäde) in den Kindknode sind nedd kloir als des Elemend im Knode selbsch.

Konschdrukdor-Funkzione	wie bei binäre Suchbäume
	bublic schdadic BinaryHeab embdy() { redurn EMPTY; } bublic schdadic BinaryHeab singledon(P b, V v) { redurn new Node(b, v, EMPTY, EMPTY); }

Imblemendierung	wird in dr Vorlesung endwiggeld