úÎ]xYâ&      !"#$%portable experimentalekmett@gmail.comC&'()*+,-A min-heap of values a. ./01O(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 2 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 3 O(1)0. Meld the values from two heaps into one heap. > meld (fromList [1,3,5]) (fromList [6,4,2]) = fromList [1..6] E meld (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 4O(log n)F. Delete the minimum key from the heap and return the resulting heap. 0 deleteMin (fromList [3,1,2]) == fromList [2,3] O(n)&. Build a heap from a list of values.  size (fromList [1,5,3]) == 3  fromList . toList = id  toList . fromList = sort 5O(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  (6 . 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)M. Construct heaps from each element in another heap, and meld them together.  concatMap (a -> fromList [a,a+1]) (fromList [1,4]) == fromList [1,2,4,5]  O(n log n)E. Group a heap into a heap of heaps, by melding 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 7 side-effects. % O(n log n)Q. Traverse the elements of the heap in sorted order and produce a new heap using 8ic side-effects. 9:;<=>?@ABCDE&  !"#$%&  $% !"# &  !"#$%F      !"#$%&'()*+,-./01234567869:6;<=>?@ABCDEFGHIJ heaps-0.1 Data.HeapEntryprioritypayloadHeapnullsizeempty singletoninsertmeld replicateunconsviewMinminimum deleteMinfromListtoUnsortedListmap mapMonotonicfilter partitionsplittakedropsplitAtbreakspan takeWhile dropWhilenub concatMapgroupgroupBy intersect intersectWithtraversemapMForestNilConsTreeNoderankroot_forestEmpty heapDataTypefromListConstr singletonWith insertWithtrees fromListWithbase GHC.ClassesnotControl.Applicative ApplicativeGHC.BaseMonadbothonlinkskewLinkinsuniqifymeldUniq skewInsertskewMeldgetMin splitForestwithList splitWithList