initial commit ,LHHEADmaster

2 files changed, 41 insertions, 0 deletions

diff --git a/Heap/Heap.hs b/Heap/Heap.hs
new file mode 100644
index 0000000..9db1424
--- /dev/null
+++ b/Heap/Heap.hs
@@ -0,0 +1,10 @@
+module Heap where
+
+class Heap h where
+    empty :: Ord a => h a
+    isEmpty :: Ord a => h a -> Bool
+    insert :: Ord a => a -> h a -> h a
+    merge :: Ord a => h a -> h a -> h a
+    findMin :: Ord a => h a -> a
+    deleteMin :: Ord a => h a -> h a
+
diff --git a/Heap/LeftistHeap.hs b/Heap/LeftistHeap.hs
new file mode 100644
index 0000000..f00dcf4
--- /dev/null
+++ b/Heap/LeftistHeap.hs
@@ -0,0 +1,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