depq-0.1.0.0: Double-ended priority queues

Data.DEPQ

Description

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

Synopsis

# Documentation

data DEPQ p a Source #

A double-ended priority queue

Instances
 (Ord p, Eq a) => Eq (DEPQ p a) Source # Instance detailsDefined 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) Source # Instance detailsDefined in Data.DEPQ MethodsshowsPrec :: Int -> DEPQ p a -> ShowS #show :: DEPQ p a -> String #showList :: [DEPQ p a] -> ShowS # (NFData p, NFData a) => NFData (DEPQ p a) Source # Instance detailsDefined in Data.DEPQ Methodsrnf :: DEPQ p a -> () #

# Creation

empty :: DEPQ p a Source #

The empty DEPQ

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 Source #

Is the DEPQ empty ?

# Modification

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 Source #

Delete the minimum-priority element in the DEPQ

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

Delete the maximum-priority element in the DEPQ

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

Return the minimum along with a new DEPQ without that element

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

Return the maximum along with a new DEPQ without that element

# Lookup

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

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

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

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

## Top-K lookup

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

K highest-scoring entries in the DEPQ

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

K lowest-scoring entries in the DEPQ