Copyright | (c) Louis Wasserman 2010 |
---|---|

License | BSD-style |

Maintainer | libraries@haskell.org |

Stability | experimental |

Portability | portable |

Safe Haskell | None |

Language | Haskell2010 |

General purpose priority queue, supporting extract-minimum operations.

An amortized running time is given for each operation, with *n* referring
to the length of the sequence and *k* being the integral index used by
some operations. These bounds hold even in a persistent (shared) setting.

This implementation is based on a binomial heap augmented with a global root.
The spine of the heap is maintained lazily. To force the spine of the heap,
use `seqSpine`

.

This implementation does not guarantee stable behavior.

This implementation offers a number of methods of the form `xxxU`

, where `U`

stands for
unordered. No guarantees whatsoever are made on the execution or traversal order of
these functions.

- data MinQueue a
- empty :: MinQueue a
- null :: MinQueue a -> Bool
- size :: MinQueue a -> Int
- findMin :: MinQueue a -> a
- getMin :: MinQueue a -> Maybe a
- deleteMin :: Ord a => MinQueue a -> MinQueue a
- deleteFindMin :: Ord a => MinQueue a -> (a, MinQueue a)
- minView :: Ord a => MinQueue a -> Maybe (a, MinQueue a)
- singleton :: a -> MinQueue a
- insert :: Ord a => a -> MinQueue a -> MinQueue a
- insertBehind :: Ord a => a -> MinQueue a -> MinQueue a
- union :: Ord a => MinQueue a -> MinQueue a -> MinQueue a
- unions :: Ord a => [MinQueue a] -> MinQueue a
- (!!) :: Ord a => MinQueue a -> Int -> a
- take :: Ord a => Int -> MinQueue a -> [a]
- drop :: Ord a => Int -> MinQueue a -> MinQueue a
- splitAt :: Ord a => Int -> MinQueue a -> ([a], MinQueue a)
- takeWhile :: Ord a => (a -> Bool) -> MinQueue a -> [a]
- dropWhile :: Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
- span :: Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
- break :: Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a)
- filter :: Ord a => (a -> Bool) -> MinQueue a -> MinQueue a
- partition :: Ord a => (a -> Bool) -> MinQueue a -> (MinQueue a, MinQueue a)
- mapMaybe :: Ord b => (a -> Maybe b) -> MinQueue a -> MinQueue b
- mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MinQueue a -> (MinQueue b, MinQueue c)
- map :: Ord b => (a -> b) -> MinQueue a -> MinQueue b
- foldrAsc :: Ord a => (a -> b -> b) -> b -> MinQueue a -> b
- foldlAsc :: Ord a => (b -> a -> b) -> b -> MinQueue a -> b
- foldrDesc :: Ord a => (a -> b -> b) -> b -> MinQueue a -> b
- foldlDesc :: Ord a => (b -> a -> b) -> b -> MinQueue a -> b
- toList :: Ord a => MinQueue a -> [a]
- toAscList :: Ord a => MinQueue a -> [a]
- toDescList :: Ord a => MinQueue a -> [a]
- fromList :: Ord a => [a] -> MinQueue a
- fromAscList :: [a] -> MinQueue a
- fromDescList :: [a] -> MinQueue a
- mapU :: (a -> b) -> MinQueue a -> MinQueue b
- foldrU :: (a -> b -> b) -> b -> MinQueue a -> b
- foldlU :: (b -> a -> b) -> b -> MinQueue a -> b
- elemsU :: MinQueue a -> [a]
- toListU :: MinQueue a -> [a]
- keysQueue :: MinPQueue k a -> MinQueue k
- seqSpine :: MinQueue a -> b -> b

# Documentation

A priority queue with elements of type `a`

. Supports extracting the minimum element.

# Basic operations

# Query operations

findMin :: MinQueue a -> a Source #

*O(1)*. Returns the minimum element. Throws an error on an empty queue.

getMin :: MinQueue a -> Maybe a Source #

Returns the minimum element of the queue, if the queue is nonempty.

deleteMin :: Ord a => MinQueue a -> MinQueue a Source #

*O(log n)*. Deletes the minimum element. If the queue is empty, does nothing.

deleteFindMin :: Ord a => MinQueue a -> (a, MinQueue a) Source #

*O(log n)*. Extracts the minimum element. Throws an error on an empty queue.

minView :: Ord a => MinQueue a -> Maybe (a, MinQueue a) Source #

Retrieves the minimum element of the queue, and the queue stripped of that element,
or `Nothing`

if passed an empty queue.

# Construction operations

insert :: Ord a => a -> MinQueue a -> MinQueue a Source #

Amortized *O(1)*, worst-case *O(log n)*. Insert an element into the priority queue.

insertBehind :: Ord a => a -> MinQueue a -> MinQueue a Source #

Amortized *O(1)*, worst-case *O(log n)*. Insert an element into the priority queue,
putting it behind elements that compare equal to the inserted one.

union :: Ord a => MinQueue a -> MinQueue a -> MinQueue a Source #

Amortized *O(log (min(n,m)))*, worst-case *O(log (max (n,m)))*. Take the union of two priority queues.

# Subsets

## Extracting subsets

(!!) :: Ord a => MinQueue a -> Int -> a Source #

*O(k log n)*. Index (subscript) operator, starting from 0. `queue !! k`

returns the `(k+1)`

th smallest
element in the queue. Equivalent to `toAscList queue !! k`

.

drop :: Ord a => Int -> MinQueue a -> MinQueue a Source #

*O(k log n)*. `drop`

`k`

, applied to a queue `queue`

, returns `queue`

with the smallest `k`

elements deleted,
or an empty queue if `k >= size `

.`queue`

## Predicates

takeWhile :: Ord a => (a -> Bool) -> MinQueue a -> [a] Source #

`takeWhile`

, applied to a predicate `p`

and a queue `queue`

, returns the
longest prefix (possibly empty) of `queue`

of elements that satisfy `p`

.

span :: Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a) Source #

`span`

, applied to a predicate `p`

and a queue `queue`

, returns a tuple where
first element is longest prefix (possibly empty) of `queue`

of elements that
satisfy `p`

and second element is the remainder of the queue.

break :: Ord a => (a -> Bool) -> MinQueue a -> ([a], MinQueue a) Source #

`break`

, applied to a predicate `p`

and a queue `queue`

, returns a tuple where
first element is longest prefix (possibly empty) of `queue`

of elements that
*do not satisfy* `p`

and second element is the remainder of the queue.

# Filter/Map

filter :: Ord a => (a -> Bool) -> MinQueue a -> MinQueue a Source #

*O(n)*. Returns the queue with all elements not satisfying `p`

removed.

partition :: Ord a => (a -> Bool) -> MinQueue a -> (MinQueue a, MinQueue a) Source #

*O(n)*. Returns a pair where the first queue contains all elements satisfying `p`

, and the second queue
contains all elements not satisfying `p`

.

mapMaybe :: Ord b => (a -> Maybe b) -> MinQueue a -> MinQueue b Source #

*O(n)*. Map elements and collect the `Just`

results.

# Fold/Functor/Traversable variations

foldrAsc :: Ord a => (a -> b -> b) -> b -> MinQueue a -> b Source #

*O(n log n)*. Performs a right-fold on the elements of a priority queue in ascending order.

foldlAsc :: Ord a => (b -> a -> b) -> b -> MinQueue a -> b Source #

*O(n log n)*. Performs a left-fold on the elements of a priority queue in ascending order.

foldrDesc :: Ord a => (a -> b -> b) -> b -> MinQueue a -> b Source #

*O(n log n)*. Performs a right-fold on the elements of a priority queue in descending order.
`foldrDesc f z q == foldlAsc (flip f) z q`

.

foldlDesc :: Ord a => (b -> a -> b) -> b -> MinQueue a -> b Source #

*O(n log n)*. Performs a left-fold on the elements of a priority queue in descending order.
`foldlDesc f z q == foldrAsc (flip f) z q`

.

# List operations

toAscList :: Ord a => MinQueue a -> [a] Source #

*O(n log n)*. Extracts the elements of the priority queue in ascending order.

toDescList :: Ord a => MinQueue a -> [a] Source #

*O(n log n)*. Extracts the elements of the priority queue in descending order.

fromList :: Ord a => [a] -> MinQueue a Source #

*O(n)*. Constructs a priority queue from an unordered list.

fromAscList :: [a] -> MinQueue a Source #

*O(n)*. Constructs a priority queue from an ascending list. *Warning*: Does not check the precondition.

fromDescList :: [a] -> MinQueue a Source #

*O(n)*. Constructs a priority queue from an descending list. *Warning*: Does not check the precondition.

# Unordered operations

mapU :: (a -> b) -> MinQueue a -> MinQueue b Source #

Maps a function over the elements of the queue, ignoring order. This function is only safe if the function is monotonic.
This function *does not* check the precondition.

foldrU :: (a -> b -> b) -> b -> MinQueue a -> b Source #

*O(n)*. Unordered right fold on a priority queue.

foldlU :: (b -> a -> b) -> b -> MinQueue a -> b Source #

*O(n)*. Unordered left fold on a priority queue.

toListU :: MinQueue a -> [a] Source #

*O(n)*. Returns the elements of the queue, in no particular order.

# Miscellaneous operations

keysQueue :: MinPQueue k a -> MinQueue k Source #

Constructs a priority queue out of the keys of the specified `MinPQueue`

.