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

Portabilityportable
Stabilityexperimental
Maintainerlibraries@haskell.org

Data.PQueue.Max

Contents

Description

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.

Synopsis

Documentation

data MaxQueue a Source

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 fmap f on a valid 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.

Instances

Typeable1 MaxQueue 
Ord a => Eq (MaxQueue a) 
(Data a, Ord a) => Data (MaxQueue a) 
Ord a => Ord (MaxQueue a) 
Read a => Read (MaxQueue a) 
(Ord a, Show a) => Show (MaxQueue a) 
Ord a => Monoid (MaxQueue a) 

Basic operations

empty :: MaxQueue aSource

O(1). The empty priority queue.

null :: MaxQueue a -> BoolSource

O(1). Is this the empty priority queue?

size :: MaxQueue a -> IntSource

O(1). The number of elements in the queue.

Query operations

findMax :: MaxQueue a -> aSource

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

getMax :: MaxQueue a -> Maybe aSource

O(1). The top (maximum) element of the queue, if there is one.

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

singleton :: a -> MaxQueue aSource

O(1). Construct a priority queue with a single element.

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.

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

Takes the union of a list of priority queues. Equivalent to foldl union empty.

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.

dropWhile :: Ord a => (a -> Bool) -> MaxQueue a -> MaxQueue aSource

dropWhile p queue returns the queue remaining after takeWhile p queue.

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.

mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MaxQueue a -> (MaxQueue b, MaxQueue c)Source

O(n). Maps a function over the elements of the queue, and separates the Left and Right 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, ...]

foldrAsc :: 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 ascending order. foldrAsc f z q == foldlDesc (flip f) z q.

foldlAsc :: 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. foldlAsc f z q == foldrDesc (flip f) z q.

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.

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

O(n). Unordered left 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.

elemsU :: MaxQueue a -> [a]Source

Equivalent to toListU.

toListU :: MaxQueue a -> [a]Source

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

Miscellaneous operations

keysQueue :: MaxPQueue k a -> MaxQueue kSource

O(n). Constructs a priority queue from the keys of a MaxPQueue.

seqSpine :: MaxQueue a -> b -> bSource

O(log n). Forces the spine of the heap.