úÎ`C\'      !"#$%&portable experimentalekmett@gmail.comO'()*+,-./A min-heap of values a. 0123O(1). Is the heap empty? & Data.Heap.null empty == True ' Data.Heap.null (singleton 1) == False O(1)&. The number of elements in the heap.  size empty == 0  size (singleton 1) == 1  size (fromList [4,1,2]) == 3 O(1). The empty heap  empty == fromList []  size empty == 0 O(1). A heap with a single element  singleton 1 == fromList [1]  singleton 1 == insert 1 empty  size (singleton 1) == 1 4 O(1)$. Insert a new value into the heap. / insert 2 (fromList [1,3]) == fromList [3,2,1] * insert 5 empty == singleton 5 + size (insert "Item" xs) == 1 + size xs 5 O(1)0. Meld the values from two heaps into one heap. ? union (fromList [1,3,5]) (fromList [6,4,2]) = fromList [1..6] F union (fromList [1,1,1]) (fromList [1,2,1]) = fromList [1,1,1,1,1,2] O(log n)A. Create a heap consisting of multiple copies of the same value. + replicate 'a' 10 == fromList "aaaaaaaaaa" O(1)! access to the minimum element.  O(log n)& access to the remainder of the heap  same operation as   7 uncons (fromList [2,1,3]) == Just (1, fromList [3,2]) Same as   O(1) . Assumes the argument is a non- heap. ! minimum (fromList [3,1,2]) == 1 6O(log n)F. Delete the minimum key from the heap and return the resulting heap. 0 deleteMin (fromList [3,1,2]) == fromList [2,3] 7O(log n)D. Adjust the minimum key in the heap and return the resulting heap. 89:;<=>?@O(n)&. Build a heap from a list of values.  size (fromList [1,5,3]) == 3  fromList . toList = id  toList . fromList = sort A O(n log n). Perform a heap sort O(n)S. Returns the elements in the heap in some arbitrary, very likely unsorted, order. . toUnsortedList (fromList [3,1,2]) == [1,3,2] ) fromList . toUnsortedList == id O(n)b. Map a function over the heap, returning a new heap ordered appropriately for its fresh contents 6 map negate (fromList [3,1,2]) == fromList [-2,-3,-1] O(n)5. Map a monotone increasing function over the heap. 8 Provides a better constant factor for performance than ™, but no checking is performed that the function provided is monotone increasing. Misuse of this function can cause a Heap to violate the heap property. 0 map (+1) (fromList [1,2,3]) = fromList [2,3,4] 0 map (*2) (fromList [1,2,3]) = fromList [2,4,6] O(n)E. Filter the heap, retaining only values that satisfy the predicate. 0 filter (>'a') (fromList "ab") == singleton 'b' ( filter (>'x') (fromList "ab") == empty ( filter (<'a') (fromList "ab") == empty O(n)ª. Partition the heap according to a predicate. The first heap contains all elements that satisfy the predicate, the second all elements that fail the predicate. See also . A partition (>'a') (fromList "ab") (singleton 'b', singleton 'a') O(n)n. Partition the heap into heaps of the elements that are less than, equal to, and greater than a given value. P split 'h' (fromList "hello") == (singleton 'e', singleton 'h', fromList "lol")  O(n log n)(. Return a heap consisting of the least n elements of a given heap. 8 take 3 (fromList [10,2,4,1,9,8,2]) == fromList [1,2,2]  O(n log n)G. Return a heap consisting of all members of given heap except for the n least elements.  O(n log n)8. Split a heap into two heaps, the first containing the n] least elements, the latter consisting of all members of the heap except for those elements.  O(n log n).  applied to a predicate p and a heap xsE returns a tuple where the first element is a heap consisting of the & longest prefix the least elements of xs that do not satisfyH p and the second element is the remainder of the elements in the heap.  e break (\x -> x `mod` 4 == 0) (fromList [3,5,7,12,13,16]) == (fromList [3,5,7], fromList [12,13,16])  p is equivalent to  (B . p).  O(n log n).  applied to a predicate p and a heap xsE returns a tuple where the first element is a heap consisting of the 6 longest prefix the least elements of xs that satisfy pF and the second element is the remainder of the elements in the heap.  _ span (\x -> x `mod` 4 == 0) (fromList [4,8,12,14,16]) == (fromList [4,8,12],fromList [14,16])  p xs is equivalent to ( p xs, 'dropWhile p xs)  O(n log n).  applied to a predicate p and a heap xs" returns a heap consisting of the & longest prefix the least elements of xs that satisfy p. Q takeWhile (\x -> x `mod` 4 == 0) (fromList [4,8,12,14,16]) == fromList [4,8,12]  O(n log n).  p xs0 returns the suffix of the heap remaining after  p xs. P dropWhile (\x -> x `mod` 4 == 0) (fromList [4,8,12,14,16]) == fromList [14,16]  O(n log n)*. Remove duplicate entries from the heap. 0 nub (fromList [1,1,2,6,6]) == fromList [1,2,6] O(n)N. Construct heaps from each element in another heap, and union them together.  concatMap (a -> fromList [a,a+1]) (fromList [1,4]) == fromList [1,2,4,5] ! O(n log n)F. Group a heap into a heap of heaps, by unioning together duplicates. ` group (fromList "hello") == fromList [fromList "h", fromList "e", fromList "ll", fromList "o"] " O(n log n)(. Group using a user supplied function. #O(n log n + m log m)a. Intersect the values in two heaps, returning the value in the left heap that compares as equal $O(n log n + m log m)a. Intersect the values in two heaps using a function to generate the elements in the right heap. % O(n log n)Q. Traverse the elements of the heap in sorted order and produce a new heap using C side-effects. & O(n log n)Q. Traverse the elements of the heap in sorted order and produce a new heap using Dic side-effects. EFGHIJKLMNOPQ'  !"#$%&'  %& !"#$ '  !"#$%&R      !"#$%&'()*+,-./0123456789:;<=>?@ABCDBEFBGHIJKLMNOPQRSTUV heaps-0.2 Data.HeapEntryprioritypayloadHeapnullsizeempty singletoninsertunion replicateunconsviewMinminimum deleteMinfromListsorttoUnsortedListmap mapMonotonicfilter partitionsplittakedropsplitAtbreakspan takeWhile dropWhilenub concatMapgroupgroupBy intersect intersectWithtraversemapMForestNilConsTreeNoderankroot_forest ForestZipperEmpty heapDataTypefromListConstr singletonWith insertWithtrees adjustMinzipperemptyZrightZadjustZreziprootZminZminZ'heapify fromListWithbase GHC.ClassesnotControl.Applicative ApplicativeGHC.BaseMonadbothonlinkskewLinkinsuniqify unionUniq skewInsertskewMeldgetMin splitForestwithList splitWithList