Binäre Mengen (Heap) Bäume

• Datentyp
• Liste >> Heap
• Heap >> Liste

ZURÜCK ---- INHALTSVERZEICHNIS ---- WEITER

Datentyp

Grundsätzlich unterscheiden sich die Searchtrees und die Heaptrees nur durch die Anordnung des Elements im Knoten. Dieses ist nun statt zwischen den beiden Unterbäumen vor die Unterbäume verschoben wurde.

data (Ord a) => Htree a =   Null
                          | Fork a (Htree a) (Htree a)
                          deriving(Show)

Heaptrees werden aber auch geordnet eingesetzt, daher ist sicherzustellen, dass die Elemente in jedem Knoten nicht größer sind als alle Elemente in den Unterbäumen. Anders ausgedrückt sind alle Wege von der Wurzel entlang des Baumes immer in aufsteigender Folge.

Heaptrees werden für andere Zwecke als Searchtrees eingesetzt. Während Searchtrees sich für generellere Probleme wie das Einfügen und Löschen eignen, sind Heaptrees für andere Operationen, wie zum Beispiel das Suchen nach dem kleinsten Element, geeignet. Zudem bieten HeapTrees den Vorteil das zwei Bäume leicht zusammengefasst werden können, das bei SearchTrees relativ aufwendig ist.

Liste >> Heap

mkHtree :: (Ord a) => [a] -> Htree a
mkHtree [] = Null
mkHtree (x:xs) = Fork x (mkHtree ys)(mkHtree zs)
         where m       = (length (xs)) `div` 2
               (ys,zs) = splitAt m (xs)

sift :: (Ord a) => a -> Htree a -> Htree a -> Htree a
sift x Null Null = Fork x Null Null
sift x (Fork y a b) Null
      | x<=y           = Fork x (Fork y a b) Null
      |otherwise       = Fork y (sift x a b) Null
sift x Null (Fork z c d)
      | x<=z           = Fork x Null (Fork z c d)
      |otherwise       = Fork z Null (sift x c d)
sift x (Fork y a b)(Fork z c d)
      | x<=min y z     = Fork x (Fork y a b)(Fork z c d)
      | y<=min x z     = Fork y (sift x a b)(Fork z c d)
      |otherwise       = Fork z (Fork y a b)(sift x c d)

heapify :: (Ord a) => Htree a -> Htree a
heapify Null = Null
heapify (Fork x xt yt) = sift x (heapify xt)(heapify yt)

mkHeap :: (Ord a) => [a] -> Htree a
mkHeap = heapify . mkHtree

Die Funktion mkHtree erstellt auf Datentypbasis Htree einen Baum, dieser soll allerdings nicht der Auflage entsprechen, das ein Knotenelement immer kleiner ist als alle Elemente der Unterbäume. Der Baum soll nur minmale Höhe besutzen. Diese Auflage soll mittels der Funktion heapify sichergestellt werden. Dazu wird eine Konstruktorfunktion mkHeap eingeführt die das Ergebnis von mkHtree mit heapify verknüpft.

heapify wird zum Starten der Funktion sift mit den benötigten Parametern gebraucht. sift erstellt aus zwei gegebenen Bäumen und einem Element einen heapTree der der Auflage entspricht das ein Knotenelement immer kleiner ist als alle Elemente in den Unterbäumen.

       ,-
    ,--8
    |  `-
 ,--0
 |  |  ,-
 |  `--1
 |     |  ,-
 |     `--7
 |        `-
-9
 |     ,-
 |  ,--6
 |  |  `-
 `--2
    |  ,-
    `--3
       |  ,-
       `--5
          `-

drawHtree (mkHtree[9,0,8,1,7,2,6,3,5])

       ,-
    ,--8
    |  `-
 ,--1
 |  |  ,-
 |  `--7
 |     |  ,-
 |     `--9
 |        `-
-0
 |     ,-
 |  ,--6
 |  |  `-
 `--2
    |  ,-
    `--3
       |  ,-
       `--5
          `-

drawHtree (mkHeap[9,0,8,1,7,2,6,3,5])

Heap >> Liste

merge :: (Ord a) => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs)(y:ys)
      | x<=y      = x : merge xs (y:ys)
      | otherwise = y : merge (x:xs) ys

flatten :: (Ord a) => Htree a -> [a]
flatten Null = []
flatten (Fork x xt yt) = x: merge (flatten xt) (flatten yt)

Die Funktion flatten erzeugt aus dem Baum eine geordnete Liste. Dabei ist ein spezielles Augenmerk auf die Unterbäume zu legen, da diese in keiner Relation zueinander stehen. Daher müssen die erzeugten Listen der Unterbäume noch nach Größe geordnet gemergt werden.

ZURÜCK ---- INHALTSVERZEICHNIS ---- WEITER