学步园

堆是一种树型数据结构，一般组织成二叉树的形式。堆具有这样的属性，对于每一个节点，父节点上的元素大于子孙节点。具体实现可以用链表，也可以用数组。优先队列(Priority Queue)可以用堆来实现。下面介绍一种左倾树(Leftist Tree)的实现方式，参考Algorithms:a functional programming approach.

左倾树首先是堆，具有堆的属性。左倾树的每一个节点除空节点外，具有这些域：数据，距离，左子树，右子树。此处的距离不是指树的深度，而是指节点到达空节点经历的最少节点个数。规定空节点的距离是0。左倾树具有这样的特点，左子树上的距离大于等于右子树上的距离，左倾树的每一个子树都是左倾树。

左倾树一般提供这些操作：取最大值，插入一个元素，删除最大元素，归并(Merge)左倾树。插入一个元素操作，可以通过归并原左倾树和待插入元素构成的独苗来完成。删除最大元素，可以通过移除左倾树的根节点，然后归并左右子树来完成。

左倾树不是平衡树，之所以采用这种不平衡的结构是因为它归并操作比较省时，只需lgn的时间复杂度，比较容易保持堆的属性（对于每一个节点，父节点上的元素大于子孙节点）。左倾树体现了一种不平衡的美。AVL树体现平衡的美。各有各的美。

下面是实现代码：

-- LeftistTree.hs</p> <p>module LeftistTree where</p> <p>data (Ord a) => LeftistTree a = EmptyTree<br /> | LeftistTree a Int (LeftistTree a) (LeftistTree a)</p> <p>treeEmpty EmptyTree = True<br /> treeEmpty _ = False</p> <p>makeEmptyTree = EmptyTree </p> <p>distance :: (Ord a)=> LeftistTree a -> Int<br /> distance EmptyTree = 0<br /> distance (LeftistTree elem dist left right) = dist</p> <p>makeLeftistTree:: (Ord a)=> a -> LeftistTree a -> LeftistTree a -> LeftistTree a<br /> makeLeftistTree elem left right | distance left >= distance right = LeftistTree elem (distance right +1) left right<br /> | otherwise = LeftistTree elem (distance left +1) right left</p> <p>mergeLeftistTree:: (Ord a)=>LeftistTree a -> LeftistTree a -> LeftistTree a<br /> mergeLeftistTree EmptyTree right = right<br /> mergeLeftistTree left EmptyTree = left<br /> mergeLeftistTree left@(LeftistTree e1 d1 l1 r1) right@(LeftistTree e2 d2 l2 r2)<br /> | e1 >= e2 = makeLeftistTree e1 l1 (mergeLeftistTree r1 right)<br /> | otherwise = makeLeftistTree e2 l2 (mergeLeftistTree left r2)</p> <p>getMax :: (Ord a ) => LeftistTree a -> a<br /> getMax EmptyTree = error "getMax on empty tree"<br /> getMax (LeftistTree e _ _ _) = e</p> <p>insertLeftistTree::(Ord a)=>LeftistTree a -> a -> LeftistTree a<br /> insertLeftistTree tree1 a = mergeLeftistTree tree1 (makeLeftistTree a EmptyTree EmptyTree ) </p> <p>removeLeftistTree::(Ord a)=>LeftistTree a -> LeftistTree a<br /> removeLeftistTree EmptyTree = error "remove on empty tree"<br /> removeLeftistTree (LeftistTree _ _ left right) = mergeLeftistTree left right</p> <p>instance (Show a, Ord a)=> Show (LeftistTree a) where<br /> show tree = showLevel tree 0<br /> where<br /> showLevel EmptyTree level= ""<br /> showLevel (LeftistTree e d l r) level = levelSpaces level ++ show(e)++ ":" ++show(d) ++ "/r/n"<br /> ++ showLevel l (level+1)<br /> ++ showLevel r (level+1)</p> <p> levelSpaces level | level==0 = ""<br /> | otherwise = ' ':' ':' ': (levelSpaces ( level -1 ) ) </p> <p>main=test</p> <p>test = do<br /> let elems = [1,3,5,7,9,2,4,6,8,0]<br /> let tree = makeEmptyTree</p> <p> let tree1 = foldl insertLeftistTree tree elems<br /> putStrLn "tree1"<br /> print tree1<br /> putStrLn "max1"<br /> print $ getMax tree1</p> <p> let tree2 = removeLeftistTree tree1<br /> putStrLn "tree2"<br /> print tree2<br /> putStrLn "max2"<br /> print $ getMax tree2

下面是试验结果：

#>runghc LeftistTree.hs</p> <p>tree1<br /> 9:2<br /> 8:2<br /> 6:1<br /> 4:1<br /> 2:1<br /> 0:1<br /> 7:1<br /> 5:1<br /> 3:1<br /> 1:1</p> <p>max1<br /> 9<br /> tree2<br /> 8:2<br /> 7:2<br /> 5:1<br /> 3:1<br /> 1:1<br /> 0:1<br /> 6:1<br /> 4:1<br /> 2:1</p> <p>max2<br /> 8