Heap/LeftistHeap.hs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

module LeftistHeap where

import Heap

data LeftistHeap a = Empty | Branch Int a (LeftistHeap a) (LeftistHeap a)

rank Empty = 0
rank (Branch r _ _ _) = r

makeBranch x a b
    | rank a >= rank b = Branch (rank b + 1) x a b
    | otherwise = Branch (rank a + 1) x b a

instance Heap LeftistHeap where
    empty = Empty
    isEmpty Empty = True
    isEmpty _ = False

    insert x h = merge (Branch 1 x Empty Empty) h

    merge h Empty = h
    merge Empty h = h
    merge h1@(Branch _ x a1 b1) h2@(Branch _ y a2 b2)
        | x <= y = makeBranch x a1 (merge b1 h2)
        | otherwise = makeBranch y a2 (merge h1 b2)

    findMin Empty = error "empty heap"
    findMin (Branch _ x _ _) = x

    deleteMin Empty = error "empty heap"
    deleteMin (Branch _ x a b) = merge a b