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

Documentation

data DEPQ p a

A double-ended priority queue

Instances

(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

(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 ?

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

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

K lowest-scoring entries in the DEPQ