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

Stability | experimental |

Maintainer | libraries@haskell.org |

General purpose priority queue, supporting maxView-maximum operations.

An amortized running time is given for each operation, with *n* referring
to the length of the sequence and *i* 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 MaxQueue a
- empty :: MaxQueue a
- null :: MaxQueue a -> Bool
- size :: MaxQueue a -> Int
- findMax :: MaxQueue a -> a
- getMax :: MaxQueue a -> Maybe a
- deleteMax :: Ord a => MaxQueue a -> MaxQueue a
- deleteFindMax :: Ord a => MaxQueue a -> (a, MaxQueue a)
- maxView :: Ord a => MaxQueue a -> Maybe (a, MaxQueue a)
- singleton :: a -> MaxQueue a
- insert :: Ord a => a -> MaxQueue a -> MaxQueue a
- union :: Ord a => MaxQueue a -> MaxQueue a -> MaxQueue a
- unions :: Ord a => [MaxQueue a] -> MaxQueue a
- (!!) :: Ord a => MaxQueue a -> Int -> a
- take :: Ord a => Int -> MaxQueue a -> [a]
- drop :: Ord a => Int -> MaxQueue a -> MaxQueue a
- splitAt :: Ord a => Int -> MaxQueue a -> ([a], MaxQueue a)
- takeWhile :: Ord a => (a -> Bool) -> MaxQueue a -> [a]
- dropWhile :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
- span :: Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
- break :: Ord a => (a -> Bool) -> MaxQueue a -> ([a], MaxQueue a)
- filter :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue a
- partition :: Ord a => (a -> Bool) -> MaxQueue a -> (MaxQueue a, MaxQueue a)
- mapMaybe :: Ord b => (a -> Maybe b) -> MaxQueue a -> MaxQueue b
- mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MaxQueue a -> (MaxQueue b, MaxQueue c)
- map :: (a -> b) -> [a] -> [b]
- foldrAsc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
- foldlAsc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
- foldrDesc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> b
- foldlDesc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> b
- toList :: Ord a => MaxQueue a -> [a]
- toAscList :: Ord a => MaxQueue a -> [a]
- toDescList :: Ord a => MaxQueue a -> [a]
- fromList :: Ord a => [a] -> MaxQueue a
- fromAscList :: [a] -> MaxQueue a
- fromDescList :: [a] -> MaxQueue a
- mapU :: (a -> b) -> MaxQueue a -> MaxQueue b
- foldrU :: (a -> b -> b) -> b -> MaxQueue a -> b
- foldlU :: (b -> a -> b) -> b -> MaxQueue a -> b
- traverseU :: (Applicative f, Ord b) => (a -> f b) -> MaxQueue a -> f (MaxQueue b)
- elemsU :: MaxQueue a -> [a]
- toListU :: MaxQueue a -> [a]
- keysQueue :: MaxPQueue k a -> MaxQueue k
- seqSpine :: MaxQueue a -> b -> b

# Documentation

A priority queue implementation. Implemented as a wrapper around Data.PQueue.Min.
*Warning*: the `Functor`

, `Foldable`

, and `Traversable`

instances of this type *ignore ordering*.
For `Functor`

, it is guaranteed that if `f`

is a monotonic function, then

on a valid
`fmap`

f`MaxQueue`

will return a valid `MaxQueue`

. An analogous guarantee holds for `traverse`

. (Note:
if passed constant-time operations, every function in `Functor`

, `Foldable`

, and `Traversable`

will run in *O(n)*.)

If you wish to perform folds on a priority queue that respect order, use `foldrDesc`

or
`foldlDesc`

.

# Basic operations

# Query operations

findMax :: MaxQueue a -> aSource

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

deleteMax :: Ord a => MaxQueue a -> MaxQueue aSource

*O(log n)*. Deletes the maximum element of the queue. Does nothing on an empty queue.

deleteFindMax :: Ord a => MaxQueue a -> (a, MaxQueue a)Source

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

maxView :: Ord a => MaxQueue a -> Maybe (a, MaxQueue a)Source

*O(log n)*. Extract the top (maximum) element of the sequence, if there is one.

# Construction operations

insert :: Ord a => a -> MaxQueue a -> MaxQueue aSource

*O(1)*. Insert an element into the priority queue.

union :: Ord a => MaxQueue a -> MaxQueue a -> MaxQueue aSource

*O(log (min(n1,n2)))*. Take the union of two priority queues.

# Subsets

## Extracting subsets

(!!) :: Ord a => MaxQueue a -> Int -> aSource

*O(k log n)*. Returns the `(k+1)`

th largest element of the queue.

take :: Ord a => Int -> MaxQueue a -> [a]Source

*O(k log n)*. Returns the list of the `k`

largest elements of the queue, in descending order, or
all elements of the queue, if `k >= n`

.

drop :: Ord a => Int -> MaxQueue a -> MaxQueue aSource

*O(k log n)*. Returns the queue with the `k`

largest elements deleted, or the empty queue if `k >= n`

.

splitAt :: Ord a => Int -> MaxQueue a -> ([a], MaxQueue a)Source

*O(k log n)*. Equivalent to `(take k queue, drop k queue)`

.

## Predicates

takeWhile :: Ord a => (a -> Bool) -> MaxQueue 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) -> MaxQueue a -> ([a], MaxQueue 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) -> MaxQueue a -> ([a], MaxQueue 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) -> MaxQueue a -> MaxQueue aSource

*O(n)*. Returns a queue of those elements which satisfy the predicate.

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

*O(n)*. Returns a pair of queues, where the left queue contains those elements that satisfy the predicate,
and the right queue contains those that do not.

mapMaybe :: Ord b => (a -> Maybe b) -> MaxQueue a -> MaxQueue bSource

*O(n)*. Maps a function over the elements of the queue, and collects the `Just`

values.

# Fold/Functor/Traversable variations

map :: (a -> b) -> [a] -> [b]

`map`

`f xs`

is the list obtained by applying `f`

to each element
of `xs`

, i.e.,

```
map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]
map f [x1, x2, ...] == [f x1, f x2, ...]
```

foldrDesc :: Ord a => (a -> b -> b) -> b -> MaxQueue a -> bSource

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

foldlDesc :: Ord a => (b -> a -> b) -> b -> MaxQueue a -> bSource

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

# List operations

toList :: Ord a => MaxQueue a -> [a]Source

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

toAscList :: Ord a => MaxQueue a -> [a]Source

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

toDescList :: Ord a => MaxQueue a -> [a]Source

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

fromList :: Ord a => [a] -> MaxQueue aSource

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

fromAscList :: [a] -> MaxQueue aSource

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

fromDescList :: [a] -> MaxQueue aSource

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

# Unordered operations

mapU :: (a -> b) -> MaxQueue a -> MaxQueue bSource

*O(n)*. Assumes that the function it is given is monotonic, and applies this function to every element of the priority queue.
*Does not check the precondition*.

foldrU :: (a -> b -> b) -> b -> MaxQueue a -> bSource

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

traverseU :: (Applicative f, Ord b) => (a -> f b) -> MaxQueue a -> f (MaxQueue b)Source

*O(n)*. Assumes that the function it is given is monotonic, in some sense, and performs the `traverse`

operation.
If the function is not monotonic, the result is undefined.

toListU :: MaxQueue a -> [a]Source

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