Fun with binary heap trees


... [Seminar "Haskell"] ... [Inhaltsübersicht] ... [zurück] ... [weiter] ...

Analyse von Skew Heaps


Problemstellung

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
     / \
    2   4
   / \
  5   3
 / \
7  6

In diesem Fallwäre die Laufzeit also O(n).


Lösung über Credit-Verfahren

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.