Willkommen |
|
|
|
myGully |
|
|
Links |
|
|
|
Forum |
|
|
|
|
 |
31.12.15, 16:10
|
#1
|
|
Anfänger
Registriert seit: Nov 2009
Beiträge: 39
Bedankt: 8
|
[Java] Implementierung eines Fibonacci Heap
Hallo zusammen!
Kurz vor dem Jahresende hänge ich "weinend"  an einem Problem bei der Implementierung eines Fibonacci Heap (für's Studium).
Zunächst habe ich versucht mich am Pseudocode aus "Algorithmen - Eine Einführung" (Cormen) zu halten. Damit war ich allerdings nicht sonderlich erfolgreich. Dann habe ich den Pseudocode aus einer Vorlesung der Uni Hamburg (lecture2go von Prof. Dr. Matthias Rarey) in Java zu übersetzen, was aber letztlich auch nicht korrekt funktioniert.
Da es sich um eine Schul-Arbeit handelt helfen mir die im Netz verfügbaren Implementierungen wenig oder garnicht, weil dort oft sehr viel optimiert und nicht die einfachste Variante verwendet wird.
Das Problem ist folgendes:
Nach dem Einfügen mehrerer Knoten in den Heap gibt es eine lange Wurzelliste (mit allen eingefügten Knoten) [das soll wohl so sein].
Ruft man nun aber z.B. die Funktionen ExtractMin() auf, verschwinden die Knoten. Bäume werden aber keine Aufgebaut. Ich denke das Problem liegt in der Consolidate()- oder in der Link()-Funktion. Zumindest entsteht hier irgendwo während des Debugging der Fehler. Ich sitze aber nun hier und sehe den Wald vor lauter Bäumen nicht. Hoffe Ihr könnt helfen.
Ich danke allen Leserinnnen und Lesern für Ihre Zeit, wünsche einen guten Rutsch und hoffe auf einen Tipp.
Beste Grüße
pL
Hier der Code der Klasse:
PHP-Code:
public class FibonacciHeap {
public Node min;
public int n;
/************************************************************************************
* Public Functions
*/
/**
* Konstruktor für einen leeren Heap
*/
public FibonacciHeap() {
this.min = null;
this.n = 0;
}
/**
* Konstruktor für einen Heap mit einem Element x
* @param x Single Node im neuen Heap
*/
public FibonacciHeap(Node x) {
this();
this.min = x;
}
/**
* MakeHeap erzeugt einen neunen Heap, der keine Elemente enthält, und gibt diesen zurück
* @return
*/
public static FibonacciHeap MakeHeap() {
return new FibonacciHeap();
}
/**
* Insert fügt ein Element x, dessen Schlüssel bereits einen Wert zugewiesen bekommen hat
* in dem Heap H ein
*
* @param H
* @param x
*/
public void Insert(FibonacciHeap H, Node x) { //OK
CyclicListConcat(H.min, x);
if (H.min == null || x.key < H.min.key) H.min = x;
H.n++;
}
/**
* Minimum gibt einen Zeiger aus das Element im Heap H zurück, dessen Schlüssel minimal ist
* @return Zeiger auf minH
*/
public Node Minimum() { //OK
return this.min;
}
/**
* Union erzuegt einen neuen Heap, der alle Elemente der Heaps H1 und H2 enthält, und gibt diesen
* zurück. Die Heaps H1 und H2 werden durch diese Operation "zersört"
*
* @param H1 Fibonacci Heap 1
* @param H2 Fibonacci Heap 2
*
* @return Neuer Fibonacci Heap mit allen Elementen aus H1 und H2
*/
public static FibonacciHeap Union(FibonacciHeap H1, FibonacciHeap H2) { //OK
FibonacciHeap resH = MakeHeap();
resH.min = H1.min;
CyclicListConcat(resH.min, H2.min);
if ((H1.min == null) || (H2.min.key < H1.min.key)){
resH.min = H2.min;
}
resH.n = H1.n + H2.n;
return resH;
}
/**
* ExtractMin entfernt das Element mit dem minimalen Schlüssel aus dem Heap H, wobei
* ein Zeiger auf das Element zurückgegeben wird.
*
* @param H
* @return
*/
public Node ExtractMin(FibonacciHeap H) { //OK
Node z = H.min;
if (z == null) return z;
Node x = z.child;
while (x != null && x.right != x) {
Node t = x.right;
CyclicListConcat(H.min, x);
x.parent = null;
x = t;
}
z.right.left = z.left;
z.left.right = z.right;
if (z == z.right) {
H.min = null;
} else {
H.min = z.right;
Consolidate(H);
}
H.n--;
return z;
}
/**
* DecreaseKey weist dem Element x innerhalb des Heaps H den neuen Schlüssel k zu, von dem
* wir voraussetzen, dass er nicht größer als der aktuelle Schlüsselwert ist (sonst InvalidKeyException)
*
* @param H
* @param x
* @param k
* @throws fibheap.FibonacciHeap.InvalidKeyException
*/
public void DecreaseKey(FibonacciHeap H, Node x, int k) throws InvalidKeyException { //OK
if (k > x.key) {
throw new InvalidKeyException("Der neue Schlüssel ist größer als der aktuelle!");
}
x.key = k;
Node y = x.parent;
if (y != null && x.key < y.key) {
Cut(H, x, y);
CascadingCut(H, y);
}
if (x.key < H.min.key) {
H.min = x;
}
}
/**
* Löscht den Knoten x aus dem Heap H
*
* @param H bestehender Fibonacci Heap
* @param x Referenz des zu löschenden Knotens
*/
public void Delete(FibonacciHeap H, Node x) { //OK
try {
DecreaseKey(H, x, Integer.MIN_VALUE);
ExtractMin(H);
} catch (InvalidKeyException e) {
System.err.print(e.getMessage());
}
}
/************************************************************************************
* Private Functions
*/
/**
* Konkateniert zwei Elemente einer zirkularen doppelt verkettenen Liste
*
* @param x Listenkopf
* @param y anzuhängender Knoten
*/
private static void CyclicListConcat(Node x, Node y){ //OK
if (x==null) {
x = y;
} else {
Node t = x.right;
Node n = y.left;
x.right = y;
y.left = x;
t.left = n;
n.right = t;
}
}
/**
* Consolidate verkürzt die Wurzelliste durch Vereinigung der binomialen Bäume,
* bis alle Wurzeln unterschiedliche Grade aufweisen
*
* @param H Fibonacci Heap mit Strukturdefekten
*/
public void Consolidate(FibonacciHeap H) { //OK
int maxDeg = 2*log(this.n);
Node[] A = new Node[maxDeg];
for (int i=0; i<maxDeg; i++) A[i] = null;
while (H.min != null) {
Node x = H.min;
int d = x.degree;
if (x.right == x) {
H.min = null;
} else {
x.left.right = x.right;
x.right.left = x.left;
H.min = x.right;
x.right = x;
x.left = x;
}
while (A[d] != null) {
Node y = A[d];
if (x.key > y.key) Swap(x, y);
Link(H, y, x);
A[d] = null;
d++;
}
A[d] = x;
}
H.min = null;
for (int i=0; i<maxDeg; i++){
if (A[i] != null) {
if (H.min == null) {
H.min = A[i];
} else {
CyclicListConcat(H.min, A[i]);
if (A[i].key < H.min.key) H.min = A[i];
}
}
}
}
/**
* Link entfernt die Wurzel y aus der Wurzelliste und macht y zu einem Kind von x
*
* @param H
* @param y
* @param x
*/
private void Link(FibonacciHeap H, Node y, Node x) { //OK
if (x.key <= y.key) {
y.right.left = y.left;
y.left.right = y.right;
y.left = y;
y.right = y;
CyclicListConcat(x.child, y);
y.parent = x;
x.degree++;
y.mark = false;
}
}
/**
* Hilfsfunktion Cut entfernt x aus der Kindliste von y
* verringert den Grad von y
* fügt x in die Wurzelliste ein und setzt x.mark zurück
*
* @param H
* @param x
* @param y
*/
private void Cut(FibonacciHeap H, Node x, Node y) { //OK
if (x.right == x) {
y.child = null;
} else {
if (y.child == x) {
y.child = x.right;
}
x.right.left = x.left;
x.left.right = x.right;
x.right = x;
x.left = x;
}
y.degree--;
x.parent = null;
CyclicListConcat(H.min, x);
x.mark = false;
}
/**
* Hilfsfunktion CascadingCut entfernt kaskadenartig alle Vorgänger, die mehr als ein Kind
* verloren haben
*
* @param H
* @param y
*/
private void CascadingCut(FibonacciHeap H, Node y) { //OK
Node z = y.parent;
if (z != null) {
if (y.mark == false) { //Fall 1: y ist erstes getrenntes Kind
y.mark = true;
} else { //Fall 2: y ist zweites getrenntes Kind
Cut(H, y, z);
CascadingCut(H, z);
}
}
}
/************************************************************************************
* Helper Functions
*/
/**
* Exception für ungültige Schlüssel für die Methode DecreaseKey
*/
public class InvalidKeyException extends Exception {
public InvalidKeyException(String msg){
super (msg);
}
}
/**
*
* @return true wenn der Heap leer ist
*/
public boolean isEmpty() {
return min == null;
}
/**
* Vertauscht zwei Knoten miteinander
* @param y Knoten 1
* @param x Knoten 2
*/
private void Swap(Node y, Node x) {
Node t = x;
x = y;
y = t;
}
/**
* Berechnet die kleinste ganze Zahl log n mit 2^(log n) >= n
* @param n Anzahl der ELemente des Heaps
* @return kleinste ganze Zahl log n mit 2^(log n) >= n
* @author ?
* @origin http://fbim.fh-regensburg.de/~saj39122/sal/skript/progr/pr13226/FibonacciHeap.java
*/
private int log (int n) {
/* berechnet die kleinste ganze Zahl log n mit 2^(log n) >= n */
int i = 1;
int logn = 0;
while (i < n) {
i = 2*i;
logn++;
}
return logn;
}
}
public class Node<T> {
public T value;
public int key;
public int degree = 0;
public boolean mark = false;
public Node left = this;
public Node right = this;
public Node parent = null;
public Node child = null;
/**
* Erzeugt einen neuen Knoten welcher im Fibonacci-Heap eingefügt werden kann
*
* @param value Inhalt des Knotens vom Typ T
* @param key Schlüsselwert im Heap
*/
public Node(T value, int key) {
this.value = value;
this.key = key;
}
}
public class FiboHeap {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
FibonacciHeap fh = new FibonacciHeap();
for (int i=0; i<10; i++)
fh.Insert(fh, new fibheap.Node<>(i, i));
fh.ExtractMin(fh);
try {
fh.DecreaseKey(fh, fh.min.right.right, -1);
}catch ( FibonacciHeap.InvalidKeyException e ) {
System.err.println(e.getMessage());
}
}
}
|
|
|
|
06.01.16, 13:28
|
#2
|
|
Anfänger
Registriert seit: Nov 2009
Beiträge: 39
Bedankt: 8
|
[Erledigt] Implementierung eines Fibonacci Heap
Hallo!
Nachdem ich mich nochmal intensiv mit dem Thema und dem Debugger beschäftigt habe, folgt nun die Lösung des Problems für die Allgemeinheit.
In meinem ersten Code finden sich die Fehler an folgenden Stellen:
- Methode CyclicListConcat()
- Methode Consolidate()
Zu 1. (und das ist mir schon ein bisschen unangenehm):
In mehreren anderen Methoden wird CyclicListConcat() verwendet um zwei zirkulär, doppelt verketteten Listen aneinander zu hängen. Dazu habe ich die Referenzen der beiden Startknoten übergeben. Java übergibt die Parameter jedoch "by Value", sodass in der Funktion zwar der Zugriff auf das Objekt möglich ist, es aber nicht außerhalb der Methode überschrieben werden kann. Es können also nur die Inhalte des übergebenen Objektes geändert werden.
Hierbei kam es zu Fehlern wenn x == NULL war. Denn dann sollte x=y werden und dies geschah nur in der Methode. Sobald diese verlassen wurde war x immernoch == NULL.
Der ELSE-Fall, also wenn x != NULL hat funktioniert, weil dort die Attribute, also der Inhalt des Objektes verändert werden - und das geht.
Leider ist mir noch keine bessere Lösung eingefallen, als den Fall x==NULL vor Aufruf der Methode abzufangen.
Zu 2.: Durchlaufen der Wurzelliste
Die Methode durchläuft in der ersten Version die Wurzelknoten in einer while-Schleife, quasi direkt im Heap - ohne Zwischenspeicherung. Das bringt folgendes Problem mit sich:
Man stelle sich eine doppelt verkettete Liste vor:
[...] <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> [...]
Nimmt man nun den minimalen Knoten (2) als Start und verarbeitet diesen wie in der Methode vorgesehen, kann es passieren dass dieser Knoten nach der Verarbeitung garnicht mehr Teil der Wurzelliste ist. Will man am Ende der Schleife auf den nächsten Nachbarn verweisen, z.B. next = (2).right; ist zur Laufzeit nicht sichergestellt, dass NEXT auch tatsächlich der nächste Knoten der Wurzelliste ist.
Meine Lösung war daher eine Methode, die den aktuellen Heap durchläuft und z.B. Referenzen auf alle Knoten der Wurzelliste in einer ArrayList zurückliefert. Diese ArrayList durchlaufe ich dann einfach mit foreach(). Somit ist sichergestellt, dass o.g. Problem nicht auftritt.
vgl. Methode: getRootList()
Ich hoffe, dass es vielleicht irgendwann mal jemandem Hilft 
MfG pL
Und hier noch die aktuelle, lauffähige Version:
PHP-Code:
import java.util.ArrayList;
/**
* Implementierung eines Fibonacci Heap
* @param <T> Wertetyp der Knoten-Inhalte
*/
public class FibonacciHeap<T> {
public FibonacciNode min = null;
public int nodes = 0;
/**
* MakeHeap erzeugt einen neunen Heap, der keine Elemente enthält, und gibt diesen zurück
* @return
*/
public static FibonacciHeap MakeHeap() {
return new FibonacciHeap();
}
/**
* Insert fügt einen Knoten x, dessen Schlüssel bereits einen Wert zugewiesen bekommen hat
* in dem Heap H ein
*
* @param x FibonacciNode
*/
public void Insert(FibonacciNode x) {
//Wenn Heap leer, x als ersten Knoten einfügen
if (isEmpty()) {
min = x;
} else { //Wenn Heap nicht leer
CyclicListConcat(min, x);
if (x.key < min.key) { min = x; }
this.nodes++;
}
}
/**
* Minimum gibt einen Zeiger aus das Element im Heap H zurück, dessen Schlüssel minimal ist
* @return Zeiger auf Heap.min
*/
public FibonacciNode Minimum() {
return min;
}
/**
* Union erzuegt einen neuen Heap, der alle Elemente der Heaps H1 und H2 enthält, und gibt diesen
* zurück. Die Heaps H1 und H2 werden durch diese Operation "zersört"
*
* @param H1 Fibonacci Heap 1
* @param H2 Fibonacci Heap 2
*
* @return Neuer Fibonacci Heap mit allen Elementen aus H1 und H2
*/
public static FibonacciHeap Union(FibonacciHeap H1, FibonacciHeap H2) {
//Neuen Heap erzeugen
FibonacciHeap resH = MakeHeap();
//kopie von H1 auf den neuen Heap
resH.min = H1.min;
//wenn der neue Heap (also H1) == null, werden nur die Knoten aus H2 übertragen
if (resH.min == null) {
resH.min = H2.min;
} else {
//Sonst wird H2 an den neuen Heap angehängt
CyclicListConcat(resH.min, H2.min);
}
//Prüfen welcher Knoten aus H1 und H2 minimal ist
if (H1.min == null || (H2.min != null && H2.min.key < H1.min.key)) {
resH.min = H2.min;
}
//Anzahl der Knoten in beiden Heaps
resH.nodes = H1.nodes + H2.nodes;
return resH;
}
/**
* ExtractMin entfernt das Element mit dem minimalen Schlüssel aus dem Heap H, wobei
* ein Zeiger auf das Element zurückgegeben wird.
*
* @return
*/
public FibonacciNode ExtractMin() {
FibonacciNode exMin = this.min;
if (exMin != null) {
//Jedes Kind des min-Nodes in die Wurzelliste einfügen und parent = null setzen
getChildList(exMin).forEach((child) -> {
child.right.left = child.left;
child.left.right = child.right;
child.parent = null;
CyclicListConcat(this.min, child);
});
//min-Knoten aus der Wurzelliste heraustrennen
exMin.right.left = exMin.left;
exMin.left.right = exMin.right;
//Wenn nur ein einziger Knoten in der Wurzelliste, min = null (wird durch Consolidate behoben)
if (exMin == exMin.right) {
this.min = null;
} else {
//Wenn weitere Wurzelknoten vorhanden wird min einfach umgehängt
this.min = exMin.right;
Consolidate();
}
//einer weniger
this.nodes--;
}
//Referenz auf den herausgetrennten Knoten zurückgeben
return exMin;
}
/**
* DecreaseKey weist dem Element x innerhalb des Heaps den neuen Schlüssel newKey zu, von dem
* wir voraussetzen, dass er nicht größer als der aktuelle Schlüsselwert ist
*
* @param x
* @param newKey
*/
public void DecreaseKey(FibonacciNode x, int newKey) {
//Neuer Key ist nur gültig, wenn kleiner als aktueller Key
if (newKey <= x.key) {
x.key = newKey;
FibonacciNode xParent = x.parent;
//Key verringern und Knoten ausschneiden
if (xParent != null && x.key < xParent.key) {
Cut(x, xParent);
CascadingCut(xParent);
}
//minimum anpassen
if (x.key < this.min.key) this.min = x;
}
}
/**
* Löscht den Knoten x aus dem Heap
*
* @param x Referenz des zu löschenden Knotens
*/
public void Delete(FibonacciNode x) {
DecreaseKey(x, Integer.MIN_VALUE);
ExtractMin();
}
/**
* Konkateniert zwei Elemente einer zirkularen doppelt verkettenen Liste
* y wird als linker Bruder von x hinzugefügt
*
* @param x FibonacciNode
* @param y anzuhängender Knoten
*/
private static void CyclicListConcat(FibonacciNode x, FibonacciNode y){
y.left = y;
y.right = y;
FibonacciNode xLeft = x.left;
FibonacciNode yRight = y.right;
x.left = y;
y.right = x;
xLeft.right = yRight;
yRight.left = xLeft;
}
/**
* Consolidate verkürzt die Wurzelliste durch Vereinigung der binomialen Bäume,
* bis alle Wurzeln unterschiedliche Grade aufweisen
*/
private void Consolidate() {
int Dn = 2*log(this.nodes);
FibonacciNode[] A = new FibonacciNode[Dn];
for (int i=0; i<Dn; i++) A[i] = null;
//alle Wurzelknoten durchlaufen
getRootList(this).forEach((x) -> {
int deg = x.degree;
//solange im Speicherfeld ein Baum mit gleichem Degree existiert werden
//diese zusammengesetzt, sodass zwei gleiche Bäume immer direkt zum nächst
//größeren verbunden werden
while (A[deg] != null) {
FibonacciNode y = A[deg];
if (x.key > y.key) {
FibonacciNode tmp = x;
x = y;
y = tmp;
}
//beide Knoten/Bäume verknüpfen
//y wird Kind von x
Link(y, x);
A[deg] = null;
deg++;
}
//das aktuelle x (ggf. mit höherem Grad wird wieder im Speicherfeld zwischengespeichert
//falls ein weiterer Baum mit dem gleichen Degree erzeugt wird, würden diese beiden
//ebenfalls wieder zusammengefasst
A[deg] = x;
});
this.min = null;
//am Ende wird aus dem Speicherfeld der Heap wieder zusammengebaut und der
//minimale Knoten bestimmt
for (int i=0; i<Dn; i++) {
if (A[i] != null) {
if (this.min == null) {
this.min = A[i];
this.min.right = this.min;
this.min.left = this.min;
} else {
CyclicListConcat(this.min, A[i]);
if (A[i].key < this.min.key) this.min = A[i];
}
}
}
}
/**
* Link entfernt die Wurzel y aus der Wurzelliste und macht y zu einem Kind von x
*
* @param y FibonacciNode
* @param x FibonacciNode
*/
private void Link(FibonacciNode y, FibonacciNode x) {
//y aus dem Baum heraustrennen
y.right.left = y.left;
y.left.right = y.right;
y.left = y;
y.right = y;
//y als Kind von x hinzufügen
if (x.child == null) {
x.child = y;
} else {
CyclicListConcat(x.child, y);
}
//x wird Parent, x.degree wird inkrementiert, Markierung von y wird aufgehoben
y.parent = x;
x.degree++;
y.mark = false;
}
/**
* Cut entfernt x aus der Kindliste von y
* verringert den Grad von y
* fügt x in die Wurzelliste ein und setzt x.mark zurück
*
* @param x
* @param y
*/
private void Cut(FibonacciNode x, FibonacciNode y) {
//Wenn x keine Geschwister hat (also y nur EIN Kind), hat nach dem Cut y keine Kinder mehr
if (x.right == x) {
y.child = null;
} else { //Falls x Geschwister hat (also y mehrere Kinder)
//Wenn y.child genau x referenziert kann einfach auf ein Geschwister umgeschrieben werden
if (y.child == x) y.child = x.right;
//in jedem Fall kann aber x aus der Kindliste herausgetrennt werden
x.right.left = x.left;
x.left.right = x.right;
x.right = x;
x.left = x;
}
//y hat einen Knoten weniger
y.degree--;
//x wird zur Wurzelliste hinzugefügt und hat damit auch keinen Parent mehr
x.parent = null;
CyclicListConcat(this.min, x);
x.mark = false;
}
/**
* CascadingCut entfernt kaskadenartig alle Vorgänger, die mehr als ein Kind
* verloren haben
*
* @param y FibonacciNode
*/
private void CascadingCut(FibonacciNode y) {
FibonacciNode yParent = y.parent;
if (yParent != null) {
if (y.mark == false) {
y.mark = true;
} else {
Cut(y, yParent);
CascadingCut(yParent);
}
}
}
/**
* Prüft ob der Heap leer ist
* @return true wenn der Heap leer ist
*/
public boolean isEmpty() {
return min == null;
}
/**
* Gibt den Heap als formatierten Text zurück
* @return
*/
@Override public String toString() {
return min.print(0);
}
/**
* Gibt den Heap in Textform auf der Konsole aus
*/
public void printHeap() {
System.out.println("Fibonacci heap:\n");
if (min != null) {
System.out.println("minH\n |");
System.out.print(this.toString());
} else {
System.out.println("empty");
}
}
/**
* Gibt die RootList von heap zurück
* @param heap Fibonacci Heap
* @return ArrayList
*/
private static ArrayList<FibonacciNode> getRootList(FibonacciHeap heap) {
return getSiblingList(heap.min);
}
/**
* Gibt die Kindliste von n zurück
* @param n Fibonacci Node
* @return ArrayList
*/
private static ArrayList<FibonacciNode> getChildList(FibonacciNode n) {
return getSiblingList(n.child);
}
/**
* Gibt die GeschwisterListe von n zurück
* @param n Fibonacci Node
* @return ArrayList
*/
private static ArrayList<FibonacciNode> getSiblingList(FibonacciNode n) {
ArrayList<FibonacciNode> list = new ArrayList();
FibonacciNode curr = n;
FibonacciNode start = null;
//Abbruchbedingung prüft ob
//-- heap nicht leer
//-- zirkuläre doppelt verkettete liste wieder am anfang angekommen ist
while (curr != start) {
if (start == null) start = curr;
list.add(curr);
curr = curr.left;
}
//Leere ArrayList wenn Heap leer, sonst
//ArrayList mit allen Geschwistern von n
return list;
}
/**
* Fügt eine neuen Knoten anhand übergebener Werte in den Heap ein
*
* @param value zu speichernder Inhalt
* @param key Schlüsselwert
*/
public void InsertNewNode(T value, int key) {
Insert(new FibonacciNode(value, key));
}
/**
* Berechnet die kleinste ganze Zahl log n mit 2^(log n) >= n
* @param n Anzahl der ELemente des Heaps
* @return kleinste ganze Zahl log n mit 2^(log n) >= n
* @author ?
* @origin http://fbim.fh-regensburg.de/~saj39122/sal/skript/progr/pr13226/FibonacciHeap.java
*/
private int log (int n) {
/* berechnet die kleinste ganze Zahl log n mit 2^(log n) >= n */
int i = 1;
int logn = 0;
while (i < n) {
i = 2*i;
logn++;
}
return logn;
}
}
/**
* Ein Knoten-Objekt in einem Fibonacci-Heap
* @param <T> Type of value
*/
public class FibonacciNode<T> {
public T value;
public int key;
public int degree = 0;
public boolean mark = false;
public FibonacciNode left = this;
public FibonacciNode right = this;
public FibonacciNode parent = null;
public FibonacciNode child = null;
/**
* Erzeugt einen neuen Knoten welcher im Fibonacci-Heap eingefügt werden kann
*
* @param value Inhalt des Knotens vom Typ T
* @param key Schlüsselwert im Heap
*/
public FibonacciNode(T value, int key) {
this.value = value;
this.key = key;
}
/**
* Gibt den Knoten mit seinen Kindern als formatierten Text zurück (rekursiv)
* Wird die Funktion für den minimalen Knoten aufgerufen, wird der gesamte Heap zurückgegeben
*
* @param level Ebene auf der sich der Knoten im Heap befindet
* @return String
*/
public String print(int level) {
String result = "";
FibonacciNode<T> curr = this;
do {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < level; i++) {
if (i < level-1) {
sb.append(" ");
} else {
sb.append(" +----");
}
}
sb.append("(").append(String.valueOf(curr.key)).append(")").append((this.mark) ? "*\n" : "\n");
result += sb.toString();
if (curr.child != null) {
result += curr.child.print(level + 1);
}
curr = curr.right;
} while (curr != this);
return result;
}
}
import java.util.ArrayList;
public class FiboHeap {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
ArrayList input = new ArrayList();
input.add(3);
input.add(19);
input.add(21);
input.add(4);
input.add(6);
input.add(1);
input.add(17);
input.add(33);
input.add(9);
input.add(18);
input.add(29);
input.add(24);
input.add(59);
input.add(5);
input.add(25);
input.add(36);
input.add(2);
FibonacciHeap fh = new FibonacciHeap();
input.forEach((e) -> { fh.InsertNewNode(Integer.parseInt(e.toString()), Integer.parseInt(e.toString())); });
fh.ExtractMin();
fh.printHeap();
}
}
|
|
|
|
|
Folgendes Mitglied bedankte sich bei pro-logic:
|
|
Forumregeln
|
Du kannst keine neue Themen eröffnen
Du kannst keine Antworten verfassen
Du kannst keine Anhänge posten
Du kannst nicht deine Beiträge editieren
HTML-Code ist Aus.
|
|
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 20:45 Uhr.
().
|
Linear-Darstellung
