Fun with binary heap trees

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

Maxiphobic Heaps

Problemstellung

Das Ziel bei der Auswahl der Richtigen Stragie für die join Funktion ist, die Laufzeit so gering wie möglich zu halten. Das wäre in diesem Falle bestens O(log n). Der zeithungrigste Schritt in der join Funktion ist der rekursive Aufruf von merge. Aus diesem Grunde verhält sich die Zeit, die für join benötigt wird (und damit auch für merge) proportional zur Rekursionstiefe. Also ist das Ziel, die Rekursionstiefe so gering wie möglich zu halten. Dies wird am besten erreicht, wenn in der join Funktion immer die beiden Bäume an merge übergeben werden, die die wenigsten Elemente enhalten.

Definitionen und Funktionen

Um das eben beschrieben Verhalten zu erreichen, wird die Datenstruktur für Binary Heap Trees um ein zusätzliches Feld über die Größenangabe des Baumer erweitert. Die so entstehenden Bäume nennt man Maxiphobic Heaps (maxiphobic bedeutet soviel wie Größe vermeiden).

Data (Ord a) => Tree a = Null | Fork Int a (Tree a) (Tree a)

Natürlich müssen dann auch die Funktionen angepasst werden:

isEmpty   :: (Ord a) => Tree a -> Tree a
isEmpty Null         = True
isEmpty (Fork n x a b) = False

minElem   :: (Ord a) => Tree a -> a
minElem (Fork n x a b) = x

deleteMin :: (Ord a) => Tree a -> Tree a
deleteMin (Fork n x a b) = merge a b

insert    :: (Ord a) => a -> Tree a -> Tree a
insert x a = merge (Fork 1 y Null Null) a

merge     :: (Ord a) => Tree a -> Tree a -> Tree a
merge a Null                 = a
merge Null b                 = b
merge a b
    | minElem a <= minElem b = join a b
    | otherwise              = join b a

Die größte Änderung kommt der join Funktion zu, da sie anhand der Größe jetzt entscheiden muss, welche Bäume gemerged werden. Dies geschieht über eine Hilfsfunktion, die sich aus den drei Bäumen den größten heraussucht und ihn an die erste Stelle setzt. Die beiden kleineren Bäume sind also die letzten beiden (bb und cc).

join      :: (Ord a) => Tree a -> Tree a -> Tree a
join (Fork n x a b) c = Fork (n + size c) x aa (merge bb cc)
  where (aa, bb, cc) = orderBySize a b c

orderBySize a b c
    | size a == biggest = (a, b, c)
    | size b == biggest = (b, a, c)
    | size c == biggest = (c, a, b)
  where biggest = size a `max` size b `max` size c

size      :: (Ord a) => Tree a -> Int
size Null           = 0
size (Fork n x a b) = n

Laufzeit

Wenn man davon asugeht, dass die Größer der beiden zusammenzuführenden Bäume n sei, dann ist die Größe der drei Bäume in der join Funktion (a, b und c) n-1, da ja ein Element entnommen wurde, um als Wurzel des neuen Baumes zu fungieren. Da es insgesamt jetzt drei Bäume gibt, kann man davon ausgehen, dass der größte der drei Bäume mindestens die folgende Größe besitzt:

n-1
---
 3

Daraus wiederum folgt, dass sich die anderen beiden Bäume den Rest teilen müssen und somit maximal die folgende Größe haben können:

2n-2
----
 3

Was man grob runden kann zu (2/3)n.
Also folgt daraus, dass die Zeit, die dieses Verfahren benötigt, sich mit dem Logarithmus zur Basis 3/2 vergrößert. Also gilt als Zeitkomplexität O(log n)