| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
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
- 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
Insert an element
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