Priority Queues mit Binomial Heap Aufgabe

#1
Hallo zusammen,
bin in 3 semester Informatik.
ich habe eine Übung in Algorithmen und Datenstrukturen erhalten.


Aufgabe:
Ich muss die Minimum-Vorrangwarteschlangen welche mit Prioritäten eines beliebigen Typs P, der Comparable implementiert ist und zusätzlichen Daten eines beliebigen Typs D durch Binomial-Halden als generische Java-Klasse BinHeap<P extends Comparable<? super P>, D> mit folgenden öffentlichen Konstruktoren und Methoden Implementieren:


// Leere Halde erzeugen.
BinHeap ()
// Ist die Halde momentan leer?
boolean isEmpty ()
// Größe der Halde, d. h. Anzahl momentan gespeicherter Einträge liefern.
int size ()
// Enthält die Halde den Eintrag e?
boolean contains (Entry<P, D> e)
// Neuen Eintrag mit Priorität p und zusätzlichen Daten d // zur Halde hinzufügen und zurückliefern.
Entry<P, D> insert (P p, D d)
// Priorität des Eintrags e auf p verändern.
boolean changePrio (Entry<P, D> e, P p)
// Einen Eintrag mit minimaler Priorität liefern.
Entry<P, D> minimum ()
// Einen Eintrag mit minimaler Priorität liefern und aus der Halde entfernen.
Entry<P, D> extractMin ()
// Eintrag e aus der Halde entfernen.
boolean remove (Entry<P, D> e)
// Inhalt der Halde zu Testzwecken ausgeben.
void dump ()

HABE BEREITS DEN CODE BISSLE GROB ANGEFANGEN UND AUSKOMMENTIERT :D
was am einfachsten ist.
ich versteh einige maßen was ich machen muss, aber das Umsetzen in code fällt mir schwer :(
Bin schon die ganze nacht wach und kann es immer noch nicht umsetzen.
Könnt ihr mir alt helfen beim Code?

Liebe Grüße und danke im Voraus :)

Hier is der code und die Aufgabe habe ich angehängt




/ Als Binomial-Halde implementierte Minimum-Vorrangwarteschlange
// mit Prioritäten eines beliebigen Typs P (der die Schnittstelle
// Comparable<P> oder Comparable<P'> für einen Obertyp P' von P
// implementieren muss) und zusätzlichen Daten eines beliebigen Typs D.
class BinHeap <P extends Comparable<? super P>, D> {
// Eintrag einer solchen Warteschlange bzw. Halde, bestehend aus
// einer Priorität prio mit Typ P und zusätzlichen Daten data mit
// Typ D.
// Wenn der Eintrag momentan tatsächlich zu einer Halde gehört,
// verweist node auf den zugehörigen Knoten eines Binomialbaums
// dieser Halde.
public static class Entry <P, D> {
// Priorität, zusätzliche Daten und zugehöriger Knoten.
private P prio;
private D data;
private Node<P, D> node;

// Eintrag mit Priorität p und zusätzlichen Daten d erzeugen.
private Entry (P p, D d) {
prio = p;
data = d;
}

// Priorität bzw. zusätzliche Daten liefern.
public P prio () { return prio; }
public D data () { return data; }
}

// Knoten eines Binomialbaums innerhalb einer solchen Halde.
// Neben den eigentlichen Knotendaten (degree, parent, child,
// sibling), enthält der Knoten einen Verweis auf den zugehörigen
// Eintrag.
private static class Node <P, D> {
// Zugehöriger Eintrag.
private Entry<P, D> entry;

// Grad des Knotens.
private int degree;

// Vorgänger (falls vorhanden; bei einem Wurzelknoten null).
private Node<P, D> parent;

// Nachfolger mit dem größten Grad
// (falls vorhanden; bei einem Blattknoten null).
private Node<P, D> child;

// Zirkuläre Verkettung aller Nachfolger eines Knotens
// bzw. einfache Verkettung aller Wurzelknoten einer Halde,
// jeweils sortiert nach aufsteigendem Grad.
private Node<P, D> sibling;

// Knoten erzeugen, der auf den Eintrag e verweist
// und umgekehrt.
private Node (Entry<P, D> e) {
entry = e;
e.node = this;
}

// Priorität des Knotens, d. h. des zugehörigen Eintrags
// liefern.
private P prio () { return entry.prio; }
}

}

// Interaktives Testprogramm für die Klasse BinHeap.
class BinHeapTest {
public static void main (String [] args) throws java.io.IOException {
// Leere Halde mit Prioritäten des Typs String und zugehörigen
// Daten des Typs Integer erzeugen.
// (Die Implementierung muss aber nachträglich auch mit anderen
// Typen funktionieren.)
BinHeap<String, Integer> heap = new BinHeap<String, Integer>();

// Array mit allen eingefügten Einträgen, damit sie später
// für remove und changePrio verwendet werden können.
// Achtung: Obwohl die Klasse BinHeap ebenfalls Typparameter
// besitzt, schreibt man "BinHeap.Entry<String, Integer>" und
// nicht "BinHeap<String, Integer>.Entry<String, Integer>".
// Achtung: "new BinHeap.Entry [100]" führt zu einem Hinweis
// über "unchecked or unsafe operations"; die eigentlich "korrekte"
// Formulierung "new BinHeap.Entry<String, Integer> [100]"
// führt jedoch zu einem Übersetzungsfehler!
BinHeap.Entry<String, Integer> [] entrys = new BinHeap.Entry [100];

// Anzahl der bis jetzt eingefügten Einträge.
int n = 0;

// Standardeingabestrom System.in als InputStreamReader
// und diesen wiederum als BufferedReader "verpacken",
// damit man bequem zeilenweise lesen kann.
java.io.BufferedReader r = new java.io.BufferedReader(
new java.io.InputStreamReader(System.in));

// Endlosschleife.
while (true) {
// Inhalt und Größe der Halde ausgeben.
heap.dump();
System.out.println(heap.size() + " entry(s)");

// Eingabezeile vom Benutzer lesen, ggf. ausgeben (wenn das
// Programm nicht interaktiv verwendet wird) und in einzelne
// Wörter zerlegen.
// Abbruch bei Ende der Eingabe oder leerer Eingabezeile.
System.out.print(">>> ");
String line = r.readLine();
if (line == null || line.equals("")) return;
if (System.console() == null) System.out.println(line);
String [] cmd = line.split(" ");

// Fallunterscheidung anhand des ersten Worts.
switch (cmd[0]) {
case "+": // insert prio
// Die laufende Nummer n wird als zusätzliche Daten
// verwendet.
entrys[n] = heap.insert(cmd[1], n);
n++;
break;
case "-": // remove entry
heap.remove(entrys[Integer.parseInt(cmd[1])]);
break;
case "?": // minimum
BinHeap.Entry<String, Integer> e = heap.minimum();
System.out.println("--> " + e.prio() + " " + e.data());
break;
case "!": // extractMin
e = heap.extractMin();
System.out.println("--> " + e.prio() + " " + e.data());
break;
case "=": // changePrio entry prio
heap.changePrio(entrys[Integer.parseInt(cmd[1])], cmd[2]);
break;
}
}
}
}
 

Anhänge

Oben