dequeuemin in Fibonacci Heaps

Question

Ich wollte über Fibonacci Heaps fragen. Wenn ich dieses Szenario haben:

A 
| 
B 

Dann fügen wir zwei weitere Knoten C und D:

A 
| 
C 
| 
D 

Nun fügen wir E und F:

A 
|\ 
B C 
    | 
    D 

Jetzt sind wir B löschen .

Ich sah, dass es einen Baum so erzeugt:

E 
|\ 
F A 
    | 
    C 
    | 
    D 

Aber Ich verstehe nicht, warum E und F mit dem Baum verbunden sind. Nach dem, was ich gelesen habe, verbinden wir Bäume mit demselben Rang (zum Beispiel einen Baum von einem Knoten mit einem anderen Baum von einem Knoten), liege ich falsch?

Vielen Dank.

Answer 1

Wenn Sie die Knoten C und D in den ersten Fibonacci-Heap einfügen, würden Sie nicht mit dem Baum enden, den Sie gezeichnet haben. Stattdessen würden Sie diesen Haufen haben:

A C D 
    | 
    B 

Denken Sie daran, dass Fibonacci-Heaps lazily jeden neu hinzugefügte Wert auf die oberste Ebene Liste der Bäume hinzufügen und nur die Dinge auf einer Deletion verschmelzen. Wenn Sie B löschen waren, würden Sie es auf die oberste Ebene fördern, wie folgt aus:

A B C D 

Sie dann B entfernen würde:

A C D 

Nun, würden Sie die Wurzelliste scannen und verschmelzen die Bäume der gleichen Reihenfolge zusammen. Nehmen wir an, Sie die Knoten in der Reihenfolge A-Scan, C, D. Zunächst werden Sie verschmelzen A und C zusammen, wie folgt aus:

A D 
    | 
    C 

Zu diesem Zeitpunkt werden keine weiteren verschmilzt passieren, da genau es gibt eine Baum jeder Bestellung.

Wenn Sie dann in E und F hinzufügen, können Sie sie auf der obersten Ebene setzen würde, wie folgt aus:

A D E F 
    | 
    C 

Also ja, du hast recht, erhalten diese Knoten nicht in die zugegebene Baum.