Portability | portable |
---|---|

Stability | experimental |

Maintainer | ekmett@gmail.com |

Safe Haskell | Safe-Inferred |

An efficient, asymptotically optimal, implementation of a priority queues
extended with support for efficient size, and `Foldable`

*Note*: Since many function names (but not the type name) clash with
Prelude names, this module is usually imported `qualified`

, e.g.

import Data.Heap (Heap) import qualified Data.Heap as Heap

The implementation of `Heap`

is based on *bootstrapped skew binomial heaps*
as described by:

- G. Brodal and C. Okasaki , "Optimal Purely Functional Priority Queues",
*Journal of Functional Programming*6:839-857 (1996)

All time bounds are worst-case.

- data Heap a
- data Entry p a = Entry {}
- empty :: Heap a
- null :: Heap a -> Bool
- size :: Heap a -> Int
- singleton :: Ord a => a -> Heap a
- insert :: Ord a => a -> Heap a -> Heap a
- minimum :: Heap a -> a
- deleteMin :: Heap a -> Heap a
- union :: Heap a -> Heap a -> Heap a
- uncons :: Ord a => Heap a -> Maybe (a, Heap a)
- viewMin :: Ord a => Heap a -> Maybe (a, Heap a)
- mapMonotonic :: Ord b => (a -> b) -> Heap a -> Heap b
- map :: Ord b => (a -> b) -> Heap a -> Heap b
- toUnsortedList :: Heap a -> [a]
- fromList :: Ord a => [a] -> Heap a
- sort :: Ord a => [a] -> [a]
- traverse :: (Applicative t, Ord b) => (a -> t b) -> Heap a -> t (Heap b)
- mapM :: (Monad m, Ord b) => (a -> m b) -> Heap a -> m (Heap b)
- concatMap :: Ord b => (a -> Heap b) -> Heap a -> Heap b
- filter :: (a -> Bool) -> Heap a -> Heap a
- partition :: (a -> Bool) -> Heap a -> (Heap a, Heap a)
- split :: a -> Heap a -> (Heap a, Heap a, Heap a)
- break :: (a -> Bool) -> Heap a -> (Heap a, Heap a)
- span :: (a -> Bool) -> Heap a -> (Heap a, Heap a)
- take :: Int -> Heap a -> Heap a
- drop :: Int -> Heap a -> Heap a
- splitAt :: Int -> Heap a -> (Heap a, Heap a)
- takeWhile :: (a -> Bool) -> Heap a -> Heap a
- dropWhile :: (a -> Bool) -> Heap a -> Heap a
- group :: Heap a -> Heap (Heap a)
- groupBy :: (a -> a -> Bool) -> Heap a -> Heap (Heap a)
- nub :: Heap a -> Heap a
- intersect :: Heap a -> Heap a -> Heap a
- intersectWith :: Ord b => (a -> a -> b) -> Heap a -> Heap a -> Heap b
- replicate :: Ord a => a -> Int -> Heap a

# Heap Type

A min-heap of values of type `a`

.

# Entry type

explicit priority/payload tuples

# Basic functions

*O(1)*. Is the heap empty?

`>>>`

True`null empty`

`>>>`

False`null (singleton "hello")`

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

`>>>`

0`size empty`

`>>>`

1`size (singleton "hello")`

`>>>`

3`size (fromList [4,1,2])`

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

heap.

`>>>`

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

deleteMin :: Heap a -> Heap aSource

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

`>>>`

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

union :: Heap a -> Heap a -> Heap aSource

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

`>>>`

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

`>>>`

fromList [1,1,1,2,1,1]`union (fromList [1,1,1]) (fromList [1,2,1])`

uncons :: Ord a => Heap a -> Maybe (a, Heap a)Source

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`

`>>>`

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

# Transformations

mapMonotonic :: Ord b => (a -> b) -> Heap a -> Heap bSource

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

`>>>`

fromList [2,3,4]`map (+1) (fromList [1,2,3])`

`>>>`

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

map :: Ord b => (a -> b) -> Heap a -> Heap bSource

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

`>>>`

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

# To/From Lists

toUnsortedList :: Heap a -> [a]Source

*O(n)*. Returns the elements in the heap in some arbitrary, very likely unsorted, order.

`>>>`

[1,3,2]`toUnsortedList (fromList [3,1,2])`

`fromList`

`.`

`toUnsortedList`

≡`id`

traverse :: (Applicative t, Ord b) => (a -> t b) -> Heap a -> t (Heap b)Source

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

side-effects.

mapM :: (Monad m, Ord b) => (a -> m b) -> Heap a -> m (Heap b)Source

*O(n log n)*. Traverse the elements of the heap in sorted order and produce a new heap using `Monad`

ic side-effects.

concatMap :: Ord b => (a -> Heap b) -> Heap a -> Heap bSource

*O(n)*. Construct heaps from each element in another heap, and union them together.

`>>>`

fromList [1,4,5,2]`concatMap (\a -> fromList [a,a+1]) (fromList [1,4])`

# Filtering

filter :: (a -> Bool) -> Heap a -> Heap aSource

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

`>>>`

fromList "b"`filter (>'a') (fromList "ab")`

`>>>`

fromList []`filter (>'x') (fromList "ab")`

`>>>`

fromList []`filter (<'a') (fromList "ab")`

partition :: (a -> Bool) -> Heap a -> (Heap a, Heap a)Source

*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`

.

`>>>`

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

split :: a -> Heap a -> (Heap a, Heap a, Heap a)Source

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

`>>>`

(fromList "e",fromList "h",fromList "llo")`split 'h' (fromList "hello")`

break :: (a -> Bool) -> Heap a -> (Heap a, Heap a)Source

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

`>>>`

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

span :: (a -> Bool) -> Heap a -> (Heap a, Heap a)Source

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

`>>>`

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

`span`

`p xs`

is equivalent to `(`

`takeWhile`

p xs, 'dropWhile p xs)

take :: Int -> Heap a -> Heap aSource

*O(n log n)*. Return a heap consisting of the least `n`

elements of a given heap.

`>>>`

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

drop :: Int -> Heap a -> Heap aSource

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

least elements.

splitAt :: Int -> Heap a -> (Heap a, Heap a)Source

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

takeWhile :: (a -> Bool) -> Heap a -> Heap aSource

*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`

.

`>>>`

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

# Grouping

group :: Heap a -> Heap (Heap a)Source

*O(n log n)*. Group a heap into a heap of heaps, by unioning together duplicates.

`>>>`

fromList [fromList "e",fromList "h",fromList "ll",fromList "o"]`group (fromList "hello")`

groupBy :: (a -> a -> Bool) -> Heap a -> Heap (Heap a)Source

*O(n log n)*. Group using a user supplied function.

*O(n log n)*. Remove duplicate entries from the heap.

`>>>`

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

# Intersection

intersect :: Heap a -> Heap a -> Heap aSource

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

intersectWith :: Ord b => (a -> a -> b) -> Heap a -> Heap a -> Heap bSource

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