Data.Heap

A min-heap of values of type a.

Explicit priority/payload tuples. Useful to build a priority queue using a Heap, since the payload is ignored in the Eq/Ord instances.

myHeap = fromList [Entry 2 "World", Entry 1 "Hello", Entry 3 "!"]

==> foldMap payload myHeap ≡ "HelloWorld!"

O(1). The empty heap

empty ≡ fromList []

>>> size empty0

O(1). Is the heap empty?

>>> null emptyTrue

>>> null (singleton "hello")False

O(1). The number of elements in the heap.

>>> size empty0>>> size (singleton "hello")1>>> size (fromList [4,1,2])3

O(1). A heap with a single element

singleton x ≡ fromList [x]
singleton x ≡ insert x empty

>>> size (singleton "hello")1

O(1). Insert a new value into the heap.

>>> insert 2 (fromList [1,3])fromList [1,2,3]

insert x empty ≡ singleton x
size (insert x 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(log n). Adjust the minimum key in the heap and return the resulting heap.

>>> adjustMin (+1) (fromList [1,2,3])fromList [2,2,3]

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

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

Provides both O(1) access to the minimum element and O(log n) access to the remainder of the heap. This is the same operation as viewMin

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

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.

>>> mapMonotonic (+1) (fromList [1,2,3])fromList [2,3,4]>>> mapMonotonic (*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 [-3,-1,-2]

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.

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,4,5,2]

O(n). Filter the heap, retaining only values that satisfy the predicate.

>>> filter (>'a') (fromList "ab")fromList "b">>> filter (>'x') (fromList "ab")fromList []>>> filter (<'a') (fromList "ab")fromList []

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")(fromList "b",fromList "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")(fromList "e",fromList "h",fromList "llo")

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 "e",fromList "h",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' 10fromList "aaaaaaaaaa"