Werbung

  1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

Priority Queues mit Binomial Heap Aufgabe

Dieses Thema im Forum "Algorithmen und Datenstrukturen" wurde erstellt von Runcil, 26. Mai 2017.

  1. Runcil

    Runcil New Member

    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:

  2. coding-board

    coding-board Member

    Werbung
Die Seite wird geladen...
Ähnliche Themen - Priority Queues Binomial Forum Datum
Zwei Queues zu einem Stack C/C++ 3. Dezember 2009