Bisher sind wir davon ausgegangen, dass Skew Heaps lediglich ein Verbesserung der Maxiphobic Heaps sind und somit in O(log n) Zeit laufen. Ein Einfügevorgang in den folgenden Baum wäre jedoch proportional zur Anzahl der enthaltenen Elemente.
| 1 |
In diesem Fallwäre die Laufzeit also O(n).
Um dennoch zu beweisen, dass Skew Heaps eine logarithmische Zeitkomplexität
haben, gehen wir davon aus, dass die Zeit pro Aktion über alle Aktionen,
die zur Erzeugung des Baumes nötig waren gemittelt werden. Die Operation,
die nötig waren, um den obigen Baum zu erzeugen liefen alle in konstanter
Zeit ab (7, 5, 6, 3, 4, 1, 2 war die Reihenfolge der inserts). Also haben wir
genügend Zeit "übrig", um jetzt die teure insert-Operation
auszuführen.
Um dies jetzt zu beweisen, bepreisen wir jede Operation. Um sie ausführen
zu können, müssen entsprechend viele Credits vorhanden sein. Credits,
die nicht aufgebraucht wurden, werden für später zwischengespeichert
und bei Bedarf aufgebraucht für besonders teuere Operationen. Alles was
wir jetzt noch beweisen müssen ist, dass wir vor einer Operation, wie dem
Aufbau eines solchen Baumes und dem Einfügen eines weiteren Elementes lediglich
log n Credits benötigen und beim Ausführen dieser Operationen nie
zu wenig Credits haben, um eine Operation auszuführen.
Dazu definieren wir uns einen Knoten, dessen rechter Ast mindestens so groß
ist, wie sein linke als "gut". Wenn jedoch der linke größer
ist, ist dies ein "schlechter" Knoten. Jeder "schlechte"
Knoten bekommt bei seiner Erzeugung einen Credit gutgeschrieben.
Beim Zusammenführen der Bäume T1 und T2 mit den Größen
m1 und m2 erhalten wir einen neuen Baum der Größe n=m1+m2. Dieser
Prozess soll O(log m1+ log m2) = O(log n) Credits benötigen. Insgesamt
wird es für diesen Vorgang k+1 merge Aufrufe geben, wobei k Aufrufe die
join Funktion aufrufen.
Für jeden dieser k join Aufrufe gibt es zwei Möglichkeiten:
Ist der erste übergebene Knoten ist ein "schlechter" Knoten,
dann benutzen wir den gespeicherten Credit für diese Operation. Der dadurch
entstehende Knoten ist auf jeden fall ein "guter" Knoten.
Iser der erste übergebene Baum jedoch "gut", dann können
wir abhängig von der Größe des zweiten übergebenen Baumes
entweder "einen" guten oder einen "schlechten" Knoten erzeugen.
Auf jeden Fall benötigen wir für diesen Fall mindestens zwei Credits.
Einen um die Operation auszuführen und einen um diesen in dem neuen "schlechten"
Knoten zu speichern, sollte der neue Knoten ein "schlechter" sein.
Also werden wir insgesamt höchstens 2g+1 Credits benötigen. Wobei
g die Anzahl der "guten" durch join erzeugten Knoten ist. Jetzt müssen
wir noch zeigen, dass g <= (log m1 + log m2) ist.
Wenn der erste an join übergebene Knoten ein "guter" Knoten ist,
dann ist der Baum a höchstens so groß wie der Baum b. In dem rekursiven
Aufruf der join Funktion (merge a c) hat sich dadurch die Anzahl der Knoten
mindestens halbiert (ausgehend vom gesamten Baum T1). Dies kann dem Baum T1
jedoch höchstens log m1 mal passieren und dem Baum T2 höchstens log
m2 mal. Also ist unsere Aussage erfüllt und wir können daraus schliessen,
dass merge, insert und delete mit einer gemittelten Zeitkomplexität von
O(log n) arbeiten.