pqueue-1.3.2.2: Reliable, persistent, fast priority queues.

Data.PQueue.Prio.Min

Description

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

# Documentation

data MinPQueue k a Source #

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

 (Ord k, Eq a) => Eq (MinPQueue k a) Source # Methods(==) :: MinPQueue k a -> MinPQueue k a -> Bool #(/=) :: MinPQueue k a -> MinPQueue k a -> Bool # (Data k, Data a, Ord k) => Data (MinPQueue k a) Source # Methodsgfoldl :: (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 # Methodscompare :: 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 #max :: MinPQueue k a -> MinPQueue k a -> MinPQueue k a #min :: MinPQueue k a -> MinPQueue k a -> MinPQueue k a # (NFData k, NFData a) => NFData (MinPQueue k a) Source # Methodsrnf :: MinPQueue k a -> () #

# Construction

O(1). Returns the empty priority queue.

singleton :: k -> a -> MinPQueue k a Source #

O(1). Constructs a singleton priority queue.

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 #

Amortized O(1), worst-case O(log n). Insert an element with the specified key into the priority queue, putting it behind elements whos 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.

unions :: Ord k => [MinPQueue k a] -> MinPQueue k a Source #

The union of a list of queues: (unions == foldl union empty).

# Query

null :: MinPQueue k a -> Bool Source #

O(1). Checks if this priority queue is empty.

size :: MinPQueue k a -> Int Source #

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

## 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). mapKeys f q is the queue obtained by applying f to each key of q.

mapKeysMonotonic :: (k -> k') -> MinPQueue k a -> MinPQueue k' a Source #

O(n). mapKeysMonotonic f q == mapKeys f q, but only works when f 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 #