HORIZON HASKELLDocslts/ghc-9.10.x248f8f02026-10-05Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · 248f8f0 · 2026-10-05

Modulepqueue-1.5.0.0Haskell2010

Data.PQueue.Prio.Max

General purpose priority queue. Each element is associated with a key, and the priority queue supports viewing and extracting the element with the maximum key.

A worst-case bound is given for each operation. In some cases, an amortized bound is also specified; these bounds hold even in a persistent context.

This implementation is based on a binomial heap augmented with a global root.

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.

  • 1 type
  • 72 values
  • Packagepqueue-1.5.0.0
  • Exports73
  • LanguageHaskell2010
  • LicenceBSD-3-Clause
  • SourceMax.hs
newtypenewtype MaxPQueue k a
#

A priority queue where values of type a are annotated with keys of type k. The queue supports extracting the element with maximum key.

Instances14FoldableWithIndex, FunctorWithIndex, TraversableWithIndex, Functor, Foldable, Traversable, …

Construction

6 declarations
valueinsert :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a
#

Amortized O(1), worst-case O(\log n). Inserts an element with the specified key into the queue.

valueinsertBehind :: Ord k => k -> a -> MaxPQueue k a -> MaxPQueue k a
#

Deprecated. This function is not reliable.

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.

valueunion :: Ord k => MaxPQueue k a -> MaxPQueue k a -> MaxPQueue k a
#

Amortized O(\log \min(n_1,n_2)), worst-case O(\log \max(n_1,n_2)). Returns the union of the two specified queues.

Query

2 declarations
valuesize :: MaxPQueue k a -> Int
#

O(1). Returns the size of this priority queue.

Maximum view

valuefindMax :: MaxPQueue k a -> (k, a)
#

O(1). The maximal (key, element) in the queue. Calls error if empty.

valuegetMax :: MaxPQueue k a -> Maybe (k, a)
#

O(1). The maximal (key, element) in the queue, if the queue is nonempty.

valueadjustMax :: (a -> a) -> MaxPQueue k a -> MaxPQueue k a
#

O(1). Alter the value at the maximum key. If the queue is empty, does nothing.

valueupdateMax :: Ord k => (a -> Maybe a) -> MaxPQueue k a -> MaxPQueue k a
#

O(\log n). (Actually O(1) if there's no deletion.) Update the value at the maximum key. If the queue is empty, does nothing.

valuemaxView :: Ord k => MaxPQueue k a -> Maybe (a, MaxPQueue k a)
#

O(\log n). Retrieves the value associated with the maximum key of the queue, and the queue stripped of that element, or Nothing if passed an empty queue.

Traversal

0 declarations

Map

valuemap :: (a -> b) -> MaxPQueue k a -> MaxPQueue k b
#

O(n). Map a function over all values in the queue.

Fold

Traverse

Subsets

0 declarations

Indexed

valuedrop :: Ord k => Int -> MaxPQueue k a -> MaxPQueue k a
#

O(k \log n)/. Deletes the first k (key, value) pairs in the queue, or returns an empty queue if k >= n.

Predicates

Filter

valuepartition
  1. :: Ord k
  2. => a -> Bool
  3. -> MaxPQueue k a
  4. -> (MaxPQueue k a, MaxPQueue k a)
#

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.

valuepartitionWithKey
  1. :: Ord k
  2. => k -> a -> Bool
  3. -> MaxPQueue k a
  4. -> (MaxPQueue k a, MaxPQueue k a)
#

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.

List operations

0 declarations

Conversion from lists

valuefromList :: Ord k => [(k, a)] -> MaxPQueue k a
#

O(n). Build a priority queue from the list of (key, value) pairs.

valuefromAscList :: [(k, a)] -> MaxPQueue k a
#

O(n). Build a priority queue from an ascending list of (key, value) pairs. The precondition is not checked.

valuefromDescList :: [(k, a)] -> MaxPQueue k a
#

O(n). Build a priority queue from a descending list of (key, value) pairs. The precondition is not checked.

Conversion to lists

valuekeys :: Ord k => MaxPQueue k a -> [k]
#

O(n \log n). Return all keys of the queue in descending order.

valueelems :: Ord k => MaxPQueue k a -> [a]
#

O(n \log n). Return all elements of the queue in descending order by key.

valuetoAscList :: Ord k => MaxPQueue k a -> [(k, a)]
#

O(n \log n). Return all (key, value) pairs in ascending order by key.

valuetoDescList :: Ord k => MaxPQueue k a -> [(k, a)]
#

O(n \log n). Return all (key, value) pairs in descending order by key.

Unordered operations

13 declarations
valuefoldrU :: (a -> b -> b) -> b -> MaxPQueue k a -> b
#

O(n). An unordered right fold over the elements of the queue, in no particular order.

valuefoldrWithKeyU :: (k -> a -> b -> b) -> b -> MaxPQueue k a -> b
#

O(n). An unordered right fold over the elements of the queue, in no particular order.

valuefoldMapWithKeyU :: Monoid m => (k -> a -> m) -> MaxPQueue k a -> m
#

O(n). An unordered monoidal fold over the elements of the queue, in no particular order.

valuefoldlU :: (b -> a -> b) -> b -> MaxPQueue k a -> b
#

O(n). An unordered left fold over the elements of the queue, in no particular order. This is rarely what you want; foldrU and foldlU' are more likely to perform well.

valuefoldlU' :: (b -> a -> b) -> b -> MaxPQueue k a -> b
#

O(n). An unordered strict left fold over the elements of the queue, in no particular order.

valuefoldlWithKeyU :: (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
#

O(n). An unordered left fold over the elements of the queue, in no particular order. This is rarely what you want; foldrWithKeyU and foldlWithKeyU' are more likely to perform well.

valuefoldlWithKeyU' :: (b -> k -> a -> b) -> b -> MaxPQueue k a -> b
#

O(n). An unordered left fold over the elements of the queue, in no particular order.

valuetraverseU
  1. :: Applicative f
  2. => a -> f b
  3. -> MaxPQueue k a
  4. -> f (MaxPQueue k b)
#

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.

valuetraverseWithKeyU
  1. :: Applicative f
  2. => k -> a -> f b
  3. -> MaxPQueue k a
  4. -> f (MaxPQueue k b)
#

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.

valuekeysU :: MaxPQueue k a -> [k]
#

O(n). Return all keys of the queue in no particular order.

valueelemsU :: MaxPQueue k a -> [a]
#

O(n). Return all elements of the queue in no particular order.

valuetoListU :: MaxPQueue k a -> [(k, a)]
#

O(n). Returns all (key, value) pairs in the queue in no particular order.

Helper methods

1 declaration
valueseqSpine :: MaxPQueue k a -> b -> b
#

Deprecated. This function is no longer necessary or useful.

O(\log n). seqSpine q r forces the spine of q and returns r.

Note: The spine of a MaxPQueue is stored somewhat lazily. In earlier versions of this package, some operations could produce chains of thunks along the spine, occasionally necessitating manual forcing. Now, all operations are careful to force enough to avoid this problem.