wie würdet ihr eine Prioritätswarteschlange in java implementieren?
???
3 Antworten
Wenn man davon absieht, daß es bereits eien Priority-Queue gibt, vermutlich als Min-/Max-Heap.
Dann nimmste halt eine sortierte Liste, einfach aber halt wenig effizient. Binärbaum ginge auch, bringt aber nur etwas, wenn der halbwegs ausgeglichen bleibt - d.h. Du müßtest ihn reorganisieren. (Stichwort AVL-Baum)
ok vielen dank, ich habe noch eine verständnisfrage zu Listen, wenn man sie selbst implementiert
wenn ich einen neuen Knoten am anfang der liste adden will haben wir diese funktion hier immer genutzt:
public void addFront(int dataValue){
Node newNode = new Node(dataValue);
newNode.setNext(front);
front = newNode;
}
ein Node hat int datavalue und Node next als attribute und die liste an sich hat als attribut noch Node front; also den zeigerknoten
es wird ein neuer knoten erstellt, der value ist auf datavalue und next ist null
danach wird next von dem neuen knoten auf front gesetzt, es zeigt also auf null
dann wird front gleich dem neuen knoten gesetzt
worauf zeigt front jetzt?
zeigt newNode jetzt immernoch auf null ?
Der neue Knoten bekommt den bisherigen vordersten Knoten als NAchfolger eingetragen und er selbst wird zum neuen vordersten Knoten. front zeigt also auf den soeben hinzugefügten Knoten.
Das heißt es gibt 2 knoten die beide datavalue haben ?
Nein, lies doch einfach was da steht:
Neuen Knoten erzeugen, Datenwert zuweisen, bisheriger Frontknoten wird Nachfolger des neuen Knotens, neuer Kntoen wird Frontknoten.
Das ist ein ganz einfaches Prepending.
ahh also das überschreiben des bisherigen Frontknotens mache ich damit ich bei mehr als 1 knoten durch die Liste komme, würde ich nur 1 knoten hinzufügen bräuchte ich das nicht jetzt hab ich es
Noch eine letzte Frage: ich hab ja dann eigentlich wenn ich den ersten richtigen Knoten hinzufüge 2 Nodes aber nachdem die Methode beendet ist, wird der eine Node vom Garbage Collector entfernt oder ansonsten wäre es ja Speicherplatzverschwendung oder? Ich hätte dann also nur den Front Node mit dem datavalue
Das kommt auf die Implementierung an. Wenn keine Sentinels/Dummies genutzt werden, dann ist front bei leerer Liste einfach NULL. Beim ersten Knoten wird dieser instanziiert, der Nachfolger wird auf NULL gesetzt (entspricht Ende der Liste) und fron danach auf den neuen Knoten. Die Liste hat dann genau einen Knoten nach dem ersten Hinzufügen.
Ok hab es denke ich vielen Dank für die Hilfe 🙏
Es gibt einige Möglichkeiten, sowas zu bauen, eine eher schlechte, dafür aber sehr einfache Möglichkeit:
Eine simple Liste mit einem int pro Item, was die Priorität angibt. Bei der Suche nach dem nächsten Item sortierst Du nach der Priorität und nimmst das Item mit dem höchsten Wert. Ggf. ergänzt Du noch einen zweiten hochgezählten Wert dazu, um die Reihenfolge bei gleicher Priorität beizubehalten.
Es gibt bessere Wege, aber hier geht's allem Anschein nach um eine Studiums/Schul-Aufgabe und solange keine konkrete Arbeitsweise vorgegeben ist (wovon wir hier nichts wissen können), würde das Konzept wahrscheinlich ausreichen.
Ich würde einfach nehmen, was Java schon anbietet:
https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/PriorityQueue.html
Wenn ich es aber unbedingt selber implementieren müsste, dann vermutlich mittels binärer Suche das neue Element einfügen oder mir speichern wo die Priorität wechselt und dann dort passend einfügen.
EDIT: Wobei Binäre Suche bei einer Liste eher schwer wäre, also evtl. würde man das als Baum/Heap speichern. Oder als Ringpuffer.
... oder einfach eine simple Liste mit einem int pro Item, was die Priorität angibt. Das dann bei jeder Suche nach dem nächsten Item nach der Priorität sortieren und das Item mit dem höchsten Wert wählen. Ggf. noch einen hochgezählten zweiten Wert dazu, um die Reihenfolge in der Priorität beizubehalten.
Ist sicher nicht optimal, aber dafür ist es super einfach.
Aber klar, das Optimum ist immer, wenn man bestehende, geteteste und optimierte Implementierungen verwenden kann.
oder einfach eine simple Liste mit einem int pro Item, was die Priorität angibt
Das war der Standardfall, von dem ich ausging. Aber ich habe ja direkt effizientere, ähnlich leicht zu implementierende Alternativen genannt.
Naja, hier geht es (nach einem Kommentar und dem Profil zu urteilen) vermutlich um eine Studiumsaufgabe. Und da die Person diese Frage stellt, anstatt selber ein eine Minute in Recherche zu investieren, handelt es sich hier scheinbar um einen eher weniger motivierten blutigen Anfänger.
Sorry, wenn ich damit irgendwem auf die Füße trete, aber so wirkt es auf mich häufig.
Mit dem Kontext im Blick würde ich das nicht als "leicht" bezeichnen :)
Möglich. Aber so eine Liste zu implementieren dürfte etwa so scwher oder gar schwerer sein wie/als einen Ringpuffer oder einen Baum zu implementieren.
Oder aber er darf doch manche Sachen nutzen wie z.B. ArrayList, dann wäre es auch wurscht, dann kann er die Datenstruktur einfach wegabstrahieren.
das haben wir noch nciht darna, wir haben single linked list, double..., stack queues und binary tree