Im vorgehenden Kapitel haben wir eine Möglilchkeit gefunden, die Laufzeit
trotz Persistence über das Verfahren der gemittelten Laufzeiten gering
zu halten. Jetzt müssen wir noch den Beweis bringen, dass auch hier eine
logarithmische Zeitkomplexität gilt. Dieser ähnelt dem der "normalen"
Skew Heaps. Dieses Mal werden jedoch keine Credits sondern Debits benutzt. Sie
werden "ausgegeben" sobald eine Operation durch die Lazy Evalutaion
zurückgestellt wurde. Sobald diese Operation ausgeführt wird, wird
der Debit benutzt. Ausserdem werden wir Debits für Aktionen vergeben, die
sofort ausgeführt werden. Diese werden jedoch auch sofort wieder benutzt.
Da Haskell mit Persistence arbeitet, kann es passieren, dass wir einen Debit
zu oft benutzen. Dies bereitet jedoch keine Probleme, da diese Aktion in jedem
Falle nur einmal ausgeführt wird. Im schlimmsten Falle würden wir
also unsere Laufzeit überschätzen, was nicht wirklich problematisch
ist. Wir müssen also beweisen, dass die merge Funktion O(log n) Debits
benutzt.
Wir übernehmen die Definition von "guten" und "schlechten"
Knoten aus dem Beweis für "normale" Skew Heaps. Zu Bestimmung,
ob ein Knoten "gut" oder "schlecht" ist, zählen wir
aber alle Knoten, unabhängig davon, ob so bereits erzeugt wurden oder nicht.
Wir tun also so, also ob die Lazy Evalutation die Erzeugung von neun Knoten
nicht zurückgestellt hat. Dieses Mal sind es die "guten" Knoten,
die einen Debit aufnehmen.
Wieder mergen wir die Bäume T1 und T2 mit den Größen m1 und
m2, wobei der neue Baum die Größe n=m1+m2 hat. Wie im vorangegangenen
Beweis haben wir k+1 Aufrufe von merge, wobei diese in k Aufrufen von join resultieren.
Die beiden Fälle stellen sich dieses Mal wie folgt dar:
Haben wir einen "schlechten" Knoten, ist der entstehende Knoten auf
jeden Fall ein "guter" Knoten, dem wir einen Debit spendieren und
ihn auch dort lassen.
Haben wir jedoch einen "guten" Knoten, kann der neue Knoten wieder
"gut" oder "schlecht" sein - abhängig vom zweiten Baum.
Hier verbrauchen wir höchstens zwei Debits. Denjenigen, der sich bereits
am Knoten befindet und den, den wir benötigen für einen schlechten
Knoten.
Ausserdem brauchen wir für den letzten merge-Schritt zwei zusätzliche
Debits. Insgesamt werden wir also nie mehr als 2g+2 Debits benötigen, wobei
g wieder die Anzahl der "guten" Knoten ist. Aus dem Beweis zu den
"normalen" Skew Heaps wissen wir, dass g höchstens so groß
ist wie (log m1 + log m2). Also läuft auch nach der Lazy Evaluation der
Prozess mit einer Zeitkomplexität von O(log n).