Data.DEPQ

Double-ended priority queue (DEPQ)

Allows for efficiently finding and removing both the minimum and maximum priority elements, due to the min-heap invariant property of the underlying representation.

See https://en.wikipedia.org/wiki/Double-ended_priority_queue for definitions; the current implementation is based on the "dual structure" method outlined in the wikipedia page.

Based on IntPSQ : https://hackage.haskell.org/package/psqueues-0.2.7.2/docs/Data-IntPSQ.html

Usage

Populate a DEPQ (either from a Foldable collection such as a list or array or by inserting incrementally) and query either of its extremes (with findMin, findMax, popMin, popMax, topK, bottomK).

Note

Import this module qualified (e.g. import qualified Data.DEPQ as DQ or similar), as some of the function names are pretty common (e.g. lookup, empty), and might collide with similar functions imported from other libraries.

Documentation

data DEPQ p a

A double-ended priority queue

Instances

Foldable (DEPQ p)

Defined in Data.DEPQ

Methods

fold :: Monoid m => DEPQ p m -> m

foldMap :: Monoid m => (a -> m) -> DEPQ p a -> m

foldMap' :: Monoid m => (a -> m) -> DEPQ p a -> m

foldr :: (a -> b -> b) -> b -> DEPQ p a -> b

foldr' :: (a -> b -> b) -> b -> DEPQ p a -> b

foldl :: (b -> a -> b) -> b -> DEPQ p a -> b

foldl' :: (b -> a -> b) -> b -> DEPQ p a -> b

foldr1 :: (a -> a -> a) -> DEPQ p a -> a

foldl1 :: (a -> a -> a) -> DEPQ p a -> a

toList :: DEPQ p a -> [a]

null :: DEPQ p a -> Bool

length :: DEPQ p a -> Int

elem :: Eq a => a -> DEPQ p a -> Bool

maximum :: Ord a => DEPQ p a -> a

minimum :: Ord a => DEPQ p a -> a

sum :: Num a => DEPQ p a -> a

product :: Num a => DEPQ p a -> a

(Ord p, Eq a) => Eq (DEPQ p a)

Defined in Data.DEPQ

Methods

(==) :: DEPQ p a -> DEPQ p a -> Bool

(/=) :: DEPQ p a -> DEPQ p a -> Bool

(Show p, Show a) => Show (DEPQ p a)

Defined in Data.DEPQ

Methods

showsPrec :: Int -> DEPQ p a -> ShowS

show :: DEPQ p a -> String

showList :: [DEPQ p a] -> ShowS

(Ord p, Arbitrary p, Arbitrary a) => Arbitrary (DEPQ p a)

Defined in Data.DEPQ

Methods

arbitrary :: Gen (DEPQ p a)

shrink :: DEPQ p a -> [DEPQ p a]

(NFData p, NFData a) => NFData (DEPQ p a)

Defined in Data.DEPQ

Methods

rnf :: DEPQ p a -> ()

Creation

empty :: DEPQ p a

The empty DEPQ

Conversion from/to lists

fromList

Arguments

:: (Foldable t, Ord p)

=> t (Int, p, a)

(key, priority, value)

-> DEPQ p a

Populate a DEPQ from a Foldable container (e.g. a list)

toList :: DEPQ p v -> [(Int, p, v)]

Produce a list of (key, priority, value) triples with the entries of the DEPQ

Note : the order of the output list is undefined

Predicates

null :: DEPQ p v -> Bool

Is the DEPQ empty ?

valid :: Ord p => DEPQ p v -> Bool

Is the DEPQ valid ?

Properties

size :: DEPQ p a -> Int

Number of elements in the DEPQ

Modification

insert

Arguments

:: Ord p

=> Int

key

-> p

priority

-> a

value

-> DEPQ p a

-> DEPQ p a

Insert an element

delete

Arguments

:: Ord p

=> Int

key of the triple to be deleted

-> DEPQ p a

-> DEPQ p a

Delete a (key, priority, value) triple from the queue. When the key is not a member of the queue, the original queue is returned.

deleteMin :: Ord p => DEPQ p a -> DEPQ p a

Delete the minimum-priority element in the DEPQ

deleteMax :: Ord p => DEPQ p a -> DEPQ p a

Delete the maximum-priority element in the DEPQ

popMin :: Ord p => DEPQ p v -> Maybe ((Int, p, v), DEPQ p v)

Return the minimum along with a new DEPQ without that element

popMax :: Ord p => DEPQ p v -> Maybe ((Int, p, v), DEPQ p v)

Return the maximum along with a new DEPQ without that element

Lookup

lookup

Arguments

:: Int

lookup key

-> DEPQ p v

-> Maybe (p, v)

Lookup a key

findMin :: Ord p => DEPQ p v -> Maybe (Int, p, v)

O(1) Find the minimum-priority element in the DEPQ

findMax :: Ord p => DEPQ p v -> Maybe (Int, p, v)

O(1) Find the maximum-priority element in the DEPQ

Top-K lookup

topK :: Ord p => Int -> DEPQ p v -> Seq (Int, p, v)

K highest-scoring entries in the DEPQ

NB : this returns an empty sequence if there are fewer than K elements in the DEPQ

bottomK :: Ord p => Int -> DEPQ p v -> Seq (Int, p, v)

K lowest-scoring entries in the DEPQ

NB : this returns an empty sequence if there are fewer than K elements in the DEPQ