The document defines a leftist heap, which is a binary tree that satisfies three properties: 1) for any node X, the value of X is less than or equal to the value of its left and right children, 2) the null path length of the left child must be greater than or equal to the null path length of the right child, and 3) the null path length of a node is the shortest distance from that node to a descendant with 0 or 1 child, with a null node having a null path length of -1. An example is given to illustrate how violating the leftist heap property can be fixed by swapping children. The implementation of building a leftist heap from a list using merging is also presented
1 of 7
Downloaded 13 times
More Related Content
Purely Functional Data Structures ex3.3 leftist heap
1. Leftist Heap
Definition
A Leftist (min)Heap is a binary tree that satisfies the follow-ing conditions.
If X is a node and L and R are its left and right children, then:
每 X.value ≒ L.value
每 X.value ≒ R.value
每 null path length of L ≡ null path length of R
where the null path length of a node is the shortest distance between
from that node to a descendant with 0 or 1 child.
If a node is null, its null path length is ?1.
4. FromList及g蚾
(晟惤必奈丞 2009-11-23 Leftist Heap (http://d.hatena.ne.jp/propella/20091123/p1) 及扔件皿伙皿伕弘仿丞卞袚樓仄化妏勻化狟今中)
-- Copied from CS231 Algorithm Prof. Lyn Turbak Wellesley College
-- make a leftist heap with one node.
singleton x = T 1 x E E
-- make a leftist heap from list
fromList :: Ord a => [a] -> Heap a
fromList [] = E
fromList xs = mergeLoop (map singleton xs)
where
mergeLoop [] = error "shouldnt: mergeLoop []"
mergeLoop [t] = t
mergeLoop ts = mergeLoop(mergePairs ts)
mergePairs [] = []
mergePairs [t] = [t]
mergePairs (t1:t2:ts) = (merge t1 t2):(mergePairs ts)
prop_Heap2 :: [Int] -> Bool
prop_Heap2 xs = isSorted (heapToList (fromList xs))
test2 = verboseCheck prop_Heap2