Der Laufzeitbeweis für Skew Heaps hinkt ein wenig, wenn man von den bei
Haskell üblichen persistenten Datenstrukturen ausgeht. Wir betrachten dazu
folgendes Beispiel:
Aus dem Baum T werden 100 neue Bäume erzeugt (T100 bis T199), die jeweils
das zusätzliche Element i enthalten. Wobei i irgendein beliebiger sehr
hoher Wert ist.
| T T100
... T199 |
In diesem Falle können die Schritte zur Einfügung des i in den neuen Bäumen nicht mehr mit der Zeit gemittelt werden, die notwendig war, um den Ausgangsbaum zu erzeugen, da dieser Baum ja nur einmal aufgebaut wurde und während dieser Prozedur nur einmal Zeit gespart wurde. In diesem extremen Fall bekommen wir sogar eine Laufzeitkomplexität von O(n²), da jeder Einfügevorgang von i n Schritte benötigt.
Die Lösung für unser Problem ist eine andere Eigenart von Haskell. Die Lazy Evaluation. Durch sie benötigt der Aufruf von insert i nur noch konstante Zeit, da i nicht vollständig eingefügt wird. Der Einfügevorgang wird nur soweit ausgeführt, wie es im Moment benötigt wird. An der Stelle, wo dieser abgebrochen wird, entsteht ein so genannter potentieller Knoten, der erst bei einem Zugriff auf diesen ausgewertet wird. Das ganze sieht dann so aus, wobei das '+' der potentielle Knoten ist.
| 1 |
Wird jetzt zum Beispiel deleteMin ausgeführt, so muss dieser Knoten ausgewertet
werden. Damit verlagert sich der Rechenaufwand in die Funktion deleteMin. Aber
auch dann wird nur wieder ein Schritt ausgewertet.
Aber das alleine reicht noch nicht ganz. Es gibt noch ein weiteres Optimierungfeature
in Haskell. Wenn einmal ein potentieller Knoten ausgewertet wurde, wird dieses
Ergebnis wiederverwendet, sollte es durch einen anderen Aufruf noch einmal benötigt
werden. Das heisst, dass selbst bei vollständiger Auswertung aller 100
neuen Bäume bis zum Schluss nur einmal alle Auswertungsaktionen durchgeführt
wurden, da sie bei allen 100 Bäumen identisch sind.