Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

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

- data DEPQ p a
- empty :: DEPQ p a
- fromList :: (Foldable t, Ord p) => t (Int, p, a) -> DEPQ p a
- null :: DEPQ p v -> Bool
- insert :: Ord p => Int -> p -> a -> DEPQ p a -> DEPQ p a
- deleteMin :: Ord p => DEPQ p a -> DEPQ p a
- deleteMax :: Ord p => DEPQ p a -> DEPQ p a
- popMin :: Ord p => DEPQ p v -> Maybe ((Int, p, v), DEPQ p v)
- popMax :: Ord p => DEPQ p v -> Maybe ((Int, p, v), DEPQ p v)
- findMin :: Ord p => DEPQ p v -> Maybe (Int, p, v)
- findMax :: Ord p => DEPQ p v -> Maybe (Int, p, v)
- topK :: Ord p => Int -> DEPQ p v -> Seq (Int, p, v)
- bottomK :: Ord p => Int -> DEPQ p v -> Seq (Int, p, v)

# Documentation

A double-ended priority queue

# Creation

Populate a DEPQ from a `Foldable`

container (e.g. a list)

# Predicates

# Modification

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