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());
}
}
}
[Java] Implementierung eines Fibonacci Heap
Baum-Darstellung