Data.Seqn.PQueue

Priority queues

PQueue is a minimum priority queue implemented using an MSeq.

• It is spine-strict, and can contain only a finite number of elements.
• It is value-strict. It is guaranteed that if a PQueue is in weak head normal form (WHNF), every element of the PQueue is also in WHNF.
• It maintains insertion order. If two elements compare equal, the one which was inserted first will be removed first. Elements can also be folded over in insertion order.
• It is a mergeable priority queue. Two queues can be concatenated efficiently in logarithmic time.

It is recommended to import this module qualified to avoid name clashes.

import Data.Seqn.PQueue (PQueue)
import qualified Data.Seqn.PQueue as PQueue

PQueue

data PQueue a

A minimum priority queue.

PQueue can be used as a maximum priority queue by wrapping its elements with Down.

Instances

Foldable PQueue

length

\(O(1)\).

Folds in insertion order.

Defined in Data.Seqn.Internal.PQueue

Methods

fold :: Monoid m => PQueue m -> m

foldMap :: Monoid m => (a -> m) -> PQueue a -> m

foldMap' :: Monoid m => (a -> m) -> PQueue a -> m

foldr :: (a -> b -> b) -> b -> PQueue a -> b

foldr' :: (a -> b -> b) -> b -> PQueue a -> b

foldl :: (b -> a -> b) -> b -> PQueue a -> b

foldl' :: (b -> a -> b) -> b -> PQueue a -> b

foldr1 :: (a -> a -> a) -> PQueue a -> a

foldl1 :: (a -> a -> a) -> PQueue a -> a

toList :: PQueue a -> [a]

null :: PQueue a -> Bool

length :: PQueue a -> Int

elem :: Eq a => a -> PQueue a -> Bool

maximum :: Ord a => PQueue a -> a

minimum :: Ord a => PQueue a -> a

sum :: Num a => PQueue a -> a

product :: Num a => PQueue a -> a

Eq1 PQueue

Defined in Data.Seqn.Internal.PQueue

Methods

liftEq :: (a -> b -> Bool) -> PQueue a -> PQueue b -> Bool

Ord1 PQueue

Defined in Data.Seqn.Internal.PQueue

Methods

liftCompare :: (a -> b -> Ordering) -> PQueue a -> PQueue b -> Ordering

Show1 PQueue

Defined in Data.Seqn.Internal.PQueue

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> PQueue a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [PQueue a] -> ShowS

NFData1 PQueue

Defined in Data.Seqn.Internal.PQueue

Methods

liftRnf :: (a -> ()) -> PQueue a -> ()

FoldableWithIndex Int PQueue

Folds in insertion order.

Defined in Data.Seqn.Internal.PQueue

Methods

ifoldMap :: Monoid m => (Int -> a -> m) -> PQueue a -> m

ifoldMap' :: Monoid m => (Int -> a -> m) -> PQueue a -> m

ifoldr :: (Int -> a -> b -> b) -> b -> PQueue a -> b

ifoldl :: (Int -> b -> a -> b) -> b -> PQueue a -> b

ifoldr' :: (Int -> a -> b -> b) -> b -> PQueue a -> b

ifoldl' :: (Int -> b -> a -> b) -> b -> PQueue a -> b

Ord a => Monoid (PQueue a)

mempty

The empty queue.

Defined in Data.Seqn.Internal.PQueue

Methods

mempty :: PQueue a

mappend :: PQueue a -> PQueue a -> PQueue a

mconcat :: [PQueue a] -> PQueue a

Ord a => Semigroup (PQueue a)

(<>)

\(O(\left| \log n_1 - \log n_2 \right|)\). Concatenate two PQueues.

Defined in Data.Seqn.Internal.PQueue

Methods

(<>) :: PQueue a -> PQueue a -> PQueue a

sconcat :: NonEmpty (PQueue a) -> PQueue a

stimes :: Integral b => b -> PQueue a -> PQueue a

Ord a => IsList (PQueue a)

Defined in Data.Seqn.Internal.PQueue

Associated Types

type Item (PQueue a)

Methods

fromList :: [Item (PQueue a)] -> PQueue a

fromListN :: Int -> [Item (PQueue a)] -> PQueue a

toList :: PQueue a -> [Item (PQueue a)]

(Ord a, Read a) => Read (PQueue a)

Defined in Data.Seqn.Internal.PQueue

Methods

readsPrec :: Int -> ReadS (PQueue a)

readList :: ReadS [PQueue a]

readPrec :: ReadPrec (PQueue a)

readListPrec :: ReadPrec [PQueue a]

Show a => Show (PQueue a)

Defined in Data.Seqn.Internal.PQueue

Methods

showsPrec :: Int -> PQueue a -> ShowS

show :: PQueue a -> String

showList :: [PQueue a] -> ShowS

NFData a => NFData (PQueue a)

Defined in Data.Seqn.Internal.PQueue

Methods

rnf :: PQueue a -> ()

Eq a => Eq (PQueue a)

Insertion order.

Defined in Data.Seqn.Internal.PQueue

Methods

(==) :: PQueue a -> PQueue a -> Bool

(/=) :: PQueue a -> PQueue a -> Bool

Ord a => Ord (PQueue a)

Lexicographical ordering, in insertion order.

Defined in Data.Seqn.Internal.PQueue

Methods

compare :: PQueue a -> PQueue a -> Ordering

(<) :: PQueue a -> PQueue a -> Bool

(<=) :: PQueue a -> PQueue a -> Bool

(>) :: PQueue a -> PQueue a -> Bool

(>=) :: PQueue a -> PQueue a -> Bool

max :: PQueue a -> PQueue a -> PQueue a

min :: PQueue a -> PQueue a -> PQueue a

type Item (PQueue a)

Defined in Data.Seqn.Internal.PQueue

type Item (PQueue a) = a

empty :: PQueue a

The empty queue.

singleton :: a -> PQueue a

A singleton queue.

fromList :: Ord a => [a] -> PQueue a

\(O(n)\). Create a queue from a list.

concatMap :: (Ord b, Foldable f) => (a -> PQueue b) -> f a -> PQueue b

\(O \left(\sum_i \log n_i \right)\). Map over a Foldable and concatenate the results.

insert :: Ord a => a -> PQueue a -> PQueue a

\(O(\log n)\). Insert an element into the queue.

Note: When inserting multiple elements, it is more efficient to concatenate a fresh queue rather than repeatedly insert elements.

q <> fromList xs          -- Good
foldl' (flip insert) q xs -- Worse

min :: Ord a => PQueue a -> Maybe a

\(O(1)\). The minimum element in the queue.

minView :: Ord a => PQueue a -> Maybe (a, PQueue a)

\(O(\log n)\). The minimum element in the queue, with the rest of the queue.

toSortedList :: Ord a => PQueue a -> [a]

\(O(n \log n)\). Convert to a sorted list.

Entry

data Entry k a

A priority associated with a value. A PQueue (Entry k a) may be used when the priority is separate from the value.

Constructors

Entry !k a

Instances

Functor (Entry k)

Defined in Data.Seqn.Internal.PQueue

Methods

fmap :: (a -> b) -> Entry k a -> Entry k b

(<$) :: a -> Entry k b -> Entry k a

(Read k, Read a) => Read (Entry k a)

Defined in Data.Seqn.Internal.PQueue

Methods

readsPrec :: Int -> ReadS (Entry k a)

readList :: ReadS [Entry k a]

readPrec :: ReadPrec (Entry k a)

readListPrec :: ReadPrec [Entry k a]

(Show k, Show a) => Show (Entry k a)

Defined in Data.Seqn.Internal.PQueue

Methods

showsPrec :: Int -> Entry k a -> ShowS

show :: Entry k a -> String

showList :: [Entry k a] -> ShowS

(NFData k, NFData a) => NFData (Entry k a)

Defined in Data.Seqn.Internal.PQueue

Methods

rnf :: Entry k a -> ()

Eq k => Eq (Entry k a)

Compares by k only.

Defined in Data.Seqn.Internal.PQueue

Methods

(==) :: Entry k a -> Entry k a -> Bool

(/=) :: Entry k a -> Entry k a -> Bool

Ord k => Ord (Entry k a)

Compares by k only.

Defined in Data.Seqn.Internal.PQueue

Methods

compare :: Entry k a -> Entry k a -> Ordering

(<) :: Entry k a -> Entry k a -> Bool

(<=) :: Entry k a -> Entry k a -> Bool

(>) :: Entry k a -> Entry k a -> Bool

(>=) :: Entry k a -> Entry k a -> Bool

max :: Entry k a -> Entry k a -> Entry k a

min :: Entry k a -> Entry k a -> Entry k a

entryPrio :: Entry k a -> k

The priority.

entryValue :: Entry k a -> a

The value.