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).

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

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

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)

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

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

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