A min-heap of values a.

O(1). The empty heap

 empty == fromList []
 size empty == 0

O(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). A heap with a single element

 singleton 1 == fromList [1]
 singleton 1 == insert 1 empty
 size (singleton 1) == 1

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

O(1). Assumes the argument is a non-null heap.

 minimum (fromList [3,1,2]) == 1

O(log n). Delete the minimum key from the heap and return the resulting heap.

 deleteMin (fromList [3,1,2]) == fromList [2,3]

O(1). Meld the values from two heaps into one heap.

 union (fromList [1,3,5]) (fromList [6,4,2]) = fromList [1..6]
 union (fromList [1,1,1]) (fromList [1,2,1]) = fromList [1,1,1,1,1,2]

O(1) access to the minimum element. O(log n) access to the remainder of the heap same operation as viewMin

 uncons (fromList [2,1,3]) == Just (1, fromList [3,2])

Same as uncons

O(n). Map a monotone increasing function over the heap. Provides a better constant factor for performance than map, 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.

 map (+1) (fromList [1,2,3]) = fromList [2,3,4]
 map (*2) (fromList [1,2,3]) = fromList [2,4,6]

O(n). Map a function over the heap, returning a new heap ordered appropriately for its fresh contents

 map negate (fromList [3,1,2]) == fromList [-2,-3,-1]

O(n). 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). Build a heap from a list of values.

 size (fromList [1,5,3]) == 3
 fromList . toList = id
 toList . fromList = sort

O(n log n). Perform a heap sort

O(n log n). Traverse the elements of the heap in sorted order and produce a new heap using Applicative side-effects.

O(n log n). Traverse the elements of the heap in sorted order and produce a new heap using Monadic side-effects.

O(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). Filter the heap, retaining only values that satisfy the predicate.

 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 split.

 partition (>'a') (fromList "ab") (singleton 'b', singleton 'a')

O(n). Partition the heap into heaps of the elements that are less than, equal to, and greater than a given value.

 split 'h' (fromList "hello") == (singleton 'e', singleton 'h', fromList "lol")

O(n log n). break applied to a predicate p and a heap xs returns a tuple where the first element is a heap consisting of the longest prefix the least elements of xs that do not satisfy p and the second element is the remainder of the elements in the heap.

 break (\x -> x `mod` 4 == 0) (fromList [3,5,7,12,13,16]) == (fromList [3,5,7], fromList [12,13,16])

break p is equivalent to span (not . p).

O(n log n). span applied to a predicate p and a heap xs returns a tuple where the first element is a heap consisting of the longest prefix the least elements of xs that satisfy p 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])

span p xs is equivalent to (takeWhile p xs, 'dropWhile p xs)

O(n log n). Return a heap consisting of the least n elements of a given heap.

 take 3 (fromList [10,2,4,1,9,8,2]) == fromList [1,2,2]

O(n log n). Return a heap consisting of all members of given heap except for the n least elements.

O(n log n). 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). takeWhile 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.

 takeWhile (\x -> x `mod` 4 == 0) (fromList [4,8,12,14,16]) == fromList [4,8,12]

O(n log n). dropWhile p xs returns the suffix of the heap remaining after takeWhile p xs.

 dropWhile (\x -> x `mod` 4 == 0) (fromList [4,8,12,14,16]) == fromList [14,16]

O(n log n). 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). Remove duplicate entries from the heap.

 nub (fromList [1,1,2,6,6]) == fromList [1,2,6]

O(n log n + m log m). Intersect the values in two heaps, returning the value in the left heap that compares as equal

O(n log n + m log m). Intersect the values in two heaps using a function to generate the elements in the right heap.

O(log n). Create a heap consisting of multiple copies of the same value.

 replicate 'a' 10 == fromList "aaaaaaaaaa"