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. Each element is associated with a key, and the priority queue supports viewing and extracting the element with the minimum key.
A worst-case bound is given for each operation. In some cases, an amortized bound is also specified; these bounds do not hold in a persistent context.
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
.
We do not guarantee stable behavior.
Ties are broken arbitrarily -- that is, if k1 <= k2
and k2 <= k1
, then there
are no guarantees about the relative order in which k1
, k2
, and their associated
elements are returned. (Unlike Data.Map, we allow multiple elements with the
same key.)
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.
Synopsis
- data MinPQueue k a
- empty :: MinPQueue k a
- singleton :: k -> a -> MinPQueue k a
- insert :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
- insertBehind :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a
- union :: Ord k => MinPQueue k a -> MinPQueue k a -> MinPQueue k a
- unions :: Ord k => [MinPQueue k a] -> MinPQueue k a
- null :: MinPQueue k a -> Bool
- size :: MinPQueue k a -> Int
- findMin :: MinPQueue k a -> (k, a)
- getMin :: MinPQueue k a -> Maybe (k, a)
- deleteMin :: Ord k => MinPQueue k a -> MinPQueue k a
- deleteFindMin :: Ord k => MinPQueue k a -> ((k, a), MinPQueue k a)
- adjustMin :: (a -> a) -> MinPQueue k a -> MinPQueue k a
- adjustMinWithKey :: (k -> a -> a) -> MinPQueue k a -> MinPQueue k a
- updateMin :: Ord k => (a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
- updateMinWithKey :: Ord k => (k -> a -> Maybe a) -> MinPQueue k a -> MinPQueue k a
- minView :: Ord k => MinPQueue k a -> Maybe (a, MinPQueue k a)
- minViewWithKey :: Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a)
- map :: (a -> b) -> MinPQueue k a -> MinPQueue k b
- mapWithKey :: (k -> a -> b) -> MinPQueue k a -> MinPQueue k b
- mapKeys :: Ord k' => (k -> k') -> MinPQueue k a -> MinPQueue k' a
- mapKeysMonotonic :: (k -> k') -> MinPQueue k a -> MinPQueue k' a
- foldrWithKey :: Ord k => (k -> a -> b -> b) -> b -> MinPQueue k a -> b
- foldlWithKey :: Ord k => (b -> k -> a -> b) -> b -> MinPQueue k a -> b
- traverseWithKey :: (Ord k, Applicative f) => (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
- take :: Ord k => Int -> MinPQueue k a -> [(k, a)]
- drop :: Ord k => Int -> MinPQueue k a -> MinPQueue k a
- splitAt :: Ord k => Int -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
- takeWhile :: Ord k => (a -> Bool) -> MinPQueue k a -> [(k, a)]
- takeWhileWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> [(k, a)]
- dropWhile :: Ord k => (a -> Bool) -> MinPQueue k a -> MinPQueue k a
- dropWhileWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
- span :: Ord k => (a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
- spanWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
- break :: Ord k => (a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
- breakWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a)
- filter :: Ord k => (a -> Bool) -> MinPQueue k a -> MinPQueue k a
- filterWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a
- partition :: Ord k => (a -> Bool) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
- partitionWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a)
- mapMaybe :: Ord k => (a -> Maybe b) -> MinPQueue k a -> MinPQueue k b
- mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> MinPQueue k a -> MinPQueue k b
- mapEither :: Ord k => (a -> Either b c) -> MinPQueue k a -> (MinPQueue k b, MinPQueue k c)
- mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> MinPQueue k a -> (MinPQueue k b, MinPQueue k c)
- fromList :: Ord k => [(k, a)] -> MinPQueue k a
- fromAscList :: [(k, a)] -> MinPQueue k a
- fromDescList :: [(k, a)] -> MinPQueue k a
- keys :: Ord k => MinPQueue k a -> [k]
- elems :: Ord k => MinPQueue k a -> [a]
- assocs :: Ord k => MinPQueue k a -> [(k, a)]
- toAscList :: Ord k => MinPQueue k a -> [(k, a)]
- toDescList :: Ord k => MinPQueue k a -> [(k, a)]
- toList :: Ord k => MinPQueue k a -> [(k, a)]
- foldrU :: (a -> b -> b) -> b -> MinPQueue k a -> b
- foldrWithKeyU :: (k -> a -> b -> b) -> b -> MinPQueue k a -> b
- foldlU :: (b -> a -> b) -> b -> MinPQueue k a -> b
- foldlWithKeyU :: (b -> k -> a -> b) -> b -> MinPQueue k a -> b
- traverseU :: Applicative f => (a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
- traverseWithKeyU :: Applicative f => (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b)
- keysU :: MinPQueue k a -> [k]
- elemsU :: MinPQueue k a -> [a]
- assocsU :: MinPQueue k a -> [(k, a)]
- toListU :: MinPQueue k a -> [(k, a)]
- seqSpine :: MinPQueue k a -> b -> b
Documentation
A priority queue where values of type a
are annotated with keys of type k
.
The queue supports extracting the element with minimum key.
Instances
Functor (MinPQueue k) Source # | |
Ord k => Foldable (MinPQueue k) Source # | |
Defined in Data.PQueue.Prio.Min fold :: Monoid m => MinPQueue k m -> m # foldMap :: Monoid m => (a -> m) -> MinPQueue k a -> m # foldr :: (a -> b -> b) -> b -> MinPQueue k a -> b # foldr' :: (a -> b -> b) -> b -> MinPQueue k a -> b # foldl :: (b -> a -> b) -> b -> MinPQueue k a -> b # foldl' :: (b -> a -> b) -> b -> MinPQueue k a -> b # foldr1 :: (a -> a -> a) -> MinPQueue k a -> a # foldl1 :: (a -> a -> a) -> MinPQueue k a -> a # toList :: MinPQueue k a -> [a] # null :: MinPQueue k a -> Bool # length :: MinPQueue k a -> Int # elem :: Eq a => a -> MinPQueue k a -> Bool # maximum :: Ord a => MinPQueue k a -> a # minimum :: Ord a => MinPQueue k a -> a # | |
Ord k => Traversable (MinPQueue k) Source # | |
Defined in Data.PQueue.Prio.Min | |
(Ord k, Eq a) => Eq (MinPQueue k a) Source # | |
(Data k, Data a, Ord k) => Data (MinPQueue k a) Source # | |
Defined in Data.PQueue.Prio.Internals gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> MinPQueue k a -> c (MinPQueue k a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (MinPQueue k a) # toConstr :: MinPQueue k a -> Constr # dataTypeOf :: MinPQueue k a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (MinPQueue k a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (MinPQueue k a)) # gmapT :: (forall b. Data b => b -> b) -> MinPQueue k a -> MinPQueue k a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> MinPQueue k a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> MinPQueue k a -> r # gmapQ :: (forall d. Data d => d -> u) -> MinPQueue k a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> MinPQueue k a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> MinPQueue k a -> m (MinPQueue k a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> MinPQueue k a -> m (MinPQueue k a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> MinPQueue k a -> m (MinPQueue k a) # | |
(Ord k, Ord a) => Ord (MinPQueue k a) Source # | |
Defined in Data.PQueue.Prio.Internals compare :: MinPQueue k a -> MinPQueue k a -> Ordering # (<) :: MinPQueue k a -> MinPQueue k a -> Bool # (<=) :: MinPQueue k a -> MinPQueue k a -> Bool # (>) :: MinPQueue k a -> MinPQueue k a -> Bool # (>=) :: MinPQueue k a -> MinPQueue k a -> Bool # | |
(Read k, Read a) => Read (MinPQueue k a) Source # | |
(Ord k, Show k, Show a) => Show (MinPQueue k a) Source # | |
Ord k => Semigroup (MinPQueue k a) Source # | |
Ord k => Monoid (MinPQueue k a) Source # | |
(NFData k, NFData a) => NFData (MinPQueue k a) Source # | |
Defined in Data.PQueue.Prio.Internals |
Construction
insert :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a Source #
Amortized O(1), worst-case O(log n). Inserts an element with the specified key into the queue.
insertBehind :: Ord k => k -> a -> MinPQueue k a -> MinPQueue k a Source #
O(n) (an earlier implementation had O(1) but was buggy). Insert an element with the specified key into the priority queue, putting it behind elements whose key compares equal to the inserted one.
union :: Ord k => MinPQueue k a -> MinPQueue k a -> MinPQueue k a Source #
Amortized O(log(min(n1, n2))), worst-case O(log(max(n1, n2))). Returns the union of the two specified queues.
Query
Minimum view
findMin :: MinPQueue k a -> (k, a) Source #
O(1). The minimal (key, element) in the queue. Calls error
if empty.
getMin :: MinPQueue k a -> Maybe (k, a) Source #
O(1). The minimal (key, element) in the queue, if the queue is nonempty.
deleteMin :: Ord k => MinPQueue k a -> MinPQueue k a Source #
O(log n). Deletes the minimal (key, element) in the queue. Returns an empty queue if the queue is empty.
deleteFindMin :: Ord k => MinPQueue k a -> ((k, a), MinPQueue k a) Source #
O(log n). Delete and find the element with the minimum key. Calls error
if empty.
adjustMin :: (a -> a) -> MinPQueue k a -> MinPQueue k a Source #
O(1). Alter the value at the minimum key. If the queue is empty, does nothing.
adjustMinWithKey :: (k -> a -> a) -> MinPQueue k a -> MinPQueue k a Source #
O(1). Alter the value at the minimum key. If the queue is empty, does nothing.
updateMin :: Ord k => (a -> Maybe a) -> MinPQueue k a -> MinPQueue k a Source #
O(log n). (Actually O(1) if there's no deletion.) Update the value at the minimum key. If the queue is empty, does nothing.
updateMinWithKey :: Ord k => (k -> a -> Maybe a) -> MinPQueue k a -> MinPQueue k a Source #
O(log n). (Actually O(1) if there's no deletion.) Update the value at the minimum key. If the queue is empty, does nothing.
minView :: Ord k => MinPQueue k a -> Maybe (a, MinPQueue k a) Source #
O(log n). Retrieves the value associated with the minimal key of the queue, and the queue
stripped of that element, or Nothing
if passed an empty queue.
minViewWithKey :: Ord k => MinPQueue k a -> Maybe ((k, a), MinPQueue k a) Source #
O(log n). Retrieves the minimal (key, value) pair of the map, and the map stripped of that
element, or Nothing
if passed an empty map.
Traversal
Map
map :: (a -> b) -> MinPQueue k a -> MinPQueue k b Source #
O(n). Map a function over all values in the queue.
mapWithKey :: (k -> a -> b) -> MinPQueue k a -> MinPQueue k b Source #
O(n). Map a function over all values in the queue.
mapKeys :: Ord k' => (k -> k') -> MinPQueue k a -> MinPQueue k' a Source #
O(n).
is the queue obtained by applying mapKeys
f qf
to each key of q
.
mapKeysMonotonic :: (k -> k') -> MinPQueue k a -> MinPQueue k' a Source #
O(n).
, but only works when mapKeysMonotonic
f q == mapKeys
f qf
is strictly
monotonic. The precondition is not checked. This function has better performance than
mapKeys
.
Fold
foldrWithKey :: Ord k => (k -> a -> b -> b) -> b -> MinPQueue k a -> b Source #
O(n log n). Fold the keys and values in the map, such that
.foldrWithKey
f z q == foldr
(uncurry
f) z (toAscList
q)
If you do not care about the traversal order, consider using foldrWithKeyU
.
foldlWithKey :: Ord k => (b -> k -> a -> b) -> b -> MinPQueue k a -> b Source #
O(n log n). Fold the keys and values in the map, such that
.foldlWithKey
f z q == foldl
(uncurry
. f) z (toAscList
q)
If you do not care about the traversal order, consider using foldlWithKeyU
.
Traverse
traverseWithKey :: (Ord k, Applicative f) => (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b) Source #
O(n log n). Traverses the elements of the queue in ascending order by key.
(
)traverseWithKey
f q == fromAscList
$ traverse
(uncurry
f) (toAscList
q)
If you do not care about the order of the traversal, consider using traverseWithKeyU
.
Subsets
Indexed
drop :: Ord k => Int -> MinPQueue k a -> MinPQueue k a Source #
O(k log n). Deletes the first k
(key, value) pairs in the queue, or returns an empty queue if k >= n
.
Predicates
dropWhile :: Ord k => (a -> Bool) -> MinPQueue k a -> MinPQueue k a Source #
Removes the longest possible prefix of elements satisfying the predicate.
dropWhileWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a Source #
Removes the longest possible prefix of elements satisfying the predicate.
spanWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a) Source #
Equivalent to (
.takeWhileWithKey
p q, dropWhileWithKey
p q)
breakWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> ([(k, a)], MinPQueue k a) Source #
Equivalent to
.spanWithKey
( k a -> not
(p k a)) q
Filter
filter :: Ord k => (a -> Bool) -> MinPQueue k a -> MinPQueue k a Source #
O(n). Filter all values that satisfy the predicate.
filterWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> MinPQueue k a Source #
O(n). Filter all values that satisfy the predicate.
partition :: Ord k => (a -> Bool) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a) Source #
O(n). Partition the queue according to a predicate. The first queue contains all elements which satisfy the predicate, the second all elements that fail the predicate.
partitionWithKey :: Ord k => (k -> a -> Bool) -> MinPQueue k a -> (MinPQueue k a, MinPQueue k a) Source #
O(n). Partition the queue according to a predicate. The first queue contains all elements which satisfy the predicate, the second all elements that fail the predicate.
mapMaybe :: Ord k => (a -> Maybe b) -> MinPQueue k a -> MinPQueue k b Source #
O(n). Map values and collect the Just
results.
mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> MinPQueue k a -> MinPQueue k b Source #
O(n). Map values and collect the Just
results.
mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> MinPQueue k a -> (MinPQueue k b, MinPQueue k c) Source #
List operations
Conversion from lists
fromList :: Ord k => [(k, a)] -> MinPQueue k a Source #
O(n). Build a priority queue from the list of (key, value) pairs.
fromAscList :: [(k, a)] -> MinPQueue k a Source #
O(n). Build a priority queue from an ascending list of (key, value) pairs. The precondition is not checked.
fromDescList :: [(k, a)] -> MinPQueue k a Source #
O(n). Build a priority queue from a descending list of (key, value) pairs. The precondition is not checked.
Conversion to lists
keys :: Ord k => MinPQueue k a -> [k] Source #
O(n log n). Return all keys of the queue in ascending order.
elems :: Ord k => MinPQueue k a -> [a] Source #
O(n log n). Return all elements of the queue in ascending order by key.
toAscList :: Ord k => MinPQueue k a -> [(k, a)] Source #
O(n log n). Return all (key, value) pairs in ascending order by key.
toDescList :: Ord k => MinPQueue k a -> [(k, a)] Source #
O(n log n). Return all (key, value) pairs in descending order by key.
Unordered operations
foldrU :: (a -> b -> b) -> b -> MinPQueue k a -> b Source #
O(n). An unordered right fold over the elements of the queue, in no particular order.
foldrWithKeyU :: (k -> a -> b -> b) -> b -> MinPQueue k a -> b Source #
O(n). An unordered right fold over the elements of the queue, in no particular order.
foldlU :: (b -> a -> b) -> b -> MinPQueue k a -> b Source #
O(n). An unordered left fold over the elements of the queue, in no particular order.
foldlWithKeyU :: (b -> k -> a -> b) -> b -> MinPQueue k a -> b Source #
O(n). An unordered left fold over the elements of the queue, in no particular order.
traverseU :: Applicative f => (a -> f b) -> MinPQueue k a -> f (MinPQueue k b) Source #
O(n). An unordered traversal over a priority queue, in no particular order. While there is no guarantee in which order the elements are traversed, the resulting priority queue will be perfectly valid.
traverseWithKeyU :: Applicative f => (k -> a -> f b) -> MinPQueue k a -> f (MinPQueue k b) Source #
O(n). An unordered traversal over a priority queue, in no particular order. While there is no guarantee in which order the elements are traversed, the resulting priority queue will be perfectly valid.
elemsU :: MinPQueue k a -> [a] Source #
O(n). Return all elements of the queue in no particular order.
toListU :: MinPQueue k a -> [(k, a)] Source #
O(n). Returns all (key, value) pairs in the queue in no particular order.
Helper methods
seqSpine :: MinPQueue k a -> b -> b Source #
O(log n). Analogous to deepseq
in the deepseq
package, but only forces the spine of the binomial heap.
Orphan instances
Functor (MinPQueue k) Source # | |
Ord k => Foldable (MinPQueue k) Source # | |
fold :: Monoid m => MinPQueue k m -> m # foldMap :: Monoid m => (a -> m) -> MinPQueue k a -> m # foldr :: (a -> b -> b) -> b -> MinPQueue k a -> b # foldr' :: (a -> b -> b) -> b -> MinPQueue k a -> b # foldl :: (b -> a -> b) -> b -> MinPQueue k a -> b # foldl' :: (b -> a -> b) -> b -> MinPQueue k a -> b # foldr1 :: (a -> a -> a) -> MinPQueue k a -> a # foldl1 :: (a -> a -> a) -> MinPQueue k a -> a # toList :: MinPQueue k a -> [a] # null :: MinPQueue k a -> Bool # length :: MinPQueue k a -> Int # elem :: Eq a => a -> MinPQueue k a -> Bool # maximum :: Ord a => MinPQueue k a -> a # minimum :: Ord a => MinPQueue k a -> a # | |
Ord k => Traversable (MinPQueue k) Source # | |
(Read k, Read a) => Read (MinPQueue k a) Source # | |
(Ord k, Show k, Show a) => Show (MinPQueue k a) Source # | |
Ord k => Semigroup (MinPQueue k a) Source # | |
Ord k => Monoid (MinPQueue k a) Source # | |