Fun with binary heap trees

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

Round Robin Heaps

Problemstellung

Bei den Maxiphobic Heaps wurde bereits das Optimale an Leifzeitverhalten aus den Binary Heap Trees herausgeholt, was möglich ist. Allerdings ist die join Funktion doch recht aufwendig geraten, so dass man überlegen kann, ob es nicht auch einfacher geht. Also ohne zu Zählen.
Man kann sich da das Verfahren zu Nutze machen, das in der Regel beim Kartengeben in Kartenspiele angewendet wird. Auch hier könnte man sich aufwendig merken, wer bereits wie viele Karten bekommen hat und immer demjenigen eine Karte geben, der die wenigsten bereits bekommen hat. Es geht aber einfacher: Man verteilt die Karten einfach reih um. Und muss sich nur noch merken, wer als letztes eine Karte bekommen hat.

Definition

Das übertragen wir jetzt auf die join Funktion. Dazu bekommt jeder Ast eine "Farbe" zugeteilt, wobei in der Wurzel mitgespeichert wird, welcher Ast als nächstes an der Reihe ist, zusammengeführt zu werden. Der linke Ast ist in diesem Fall blau und der rechte rot. Des weiteren gilt für einen neu erzeugten Baum, dass zunächst der linke Ast bearbeitet wird. Also bekommt ein neuer Baum die Farbe Blau.
Die geänderte Definition und die neuen Funktionen sehen danach folgendermassen aus:

Data Color             = Blau | Rot
Data (Ord a) => Tree a = Null | Fork Color a (Tree a) (Tree a)

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

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

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

insert    :: (Ord a) => a -> Tree a -> Tree a
insert x a = merge (Fork Blau 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

join      :: (Ord a) => Tree a -> Tree a -> Tree a
join (Fork Blau x a b) c = Fork Rot x (merge a c) b
join (Fork Rot x a b) c  = Fork Blau x a (merge b c)

Skew Heaps

Dieses Verfahren ist schon sehr einfach gehalten. Aber geht es nicht noch ein wenig einfacher? Man könnte die beiden Äste als Teil eines FIFOs betrachten, in den sie nach der Bearbeitung immer wieder hineingegeben werden, so dass sich eine abwechselnde Bearbeitung ergibt. Auf diesem Wege könnte man sich den Umweg über die Farben sparen. Und genau diesen FIFO haben wir zumindest teilweise bereits mit unserer Baumstruktur definiert.
Der linke Ast wird dabei als derjenige definert, der in dem FIFO als nächstes an der Reihe ist "gemerged" zu werden. Wurde diese Operation ausgeführt, so tascht er mit dem rechten Ast die Plätze, womit der Inhalt dieses Astes als nächstes dran wäre. Der Vorteil an diesem Verfahren ist, dass die ursprüngliche Definition der Binary Heap Trees beibehalten werden kann und wir jetzt eine Antwort darauf haben, welches der sechs Verfahren aus dem ersten Kapitel das optimalste ist:

join (Fork x a b) c = Fork x b (merge a c)