From 94b9306918045e4bfde1d3ce94e1ec451c30aa2f Mon Sep 17 00:00:00 2001
From: Joe Zhao <ztuowen@gmail.com>
Date: Mon, 13 Apr 2015 15:38:12 +0800
Subject: initial commit ,LH

---
 Heap/Heap.hs        | 10 ++++++++++
 Heap/LeftistHeap.hs | 31 +++++++++++++++++++++++++++++++
 2 files changed, 41 insertions(+)
 create mode 100644 Heap/Heap.hs
 create mode 100644 Heap/LeftistHeap.hs

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
-- 
cgit v1.2.3-70-g09d2