Copyright	(c) Donnacha Oisín Kidney 2021
Maintainer	mail@doisinkidney.com
Stability	experimental
Portability	non-portable
Safe Haskell	None
Language	Haskell2010

MonusWeightedSearch.Internal.Heap

Description

A reference implementation of a pairing heap, to compare to the heap monad.

Synopsis

data Heap a b
- = Leaf
- | Node !a b [Heap a b]
minView :: Monus a => Heap a b -> Maybe ((a, b), Heap a b)
singleton :: a -> b -> Heap a b
dijkstra :: Ord a => Graph a -> Graph a
monusSort :: [Dist] -> [Dist]

Documentation

data Heap a b Source #

A pairing heap.

This implementation does use a monus rather than just a standard ordered key, but that does not change any of the algorithms really.

Constructors

Leaf
Node !a b [Heap a b]

Instances

Instances details

Functor (Heap a) Source #
Instance details Defined in MonusWeightedSearch.Internal.Heap Methods fmap :: (a0 -> b) -> Heap a a0 -> Heap a b # (<$) :: a0 -> Heap a b -> Heap a a0 #
Foldable (Heap a) Source #
Instance details Defined in MonusWeightedSearch.Internal.Heap Methods fold :: Monoid m => Heap a m -> m # foldMap :: Monoid m => (a0 -> m) -> Heap a a0 -> m # foldMap' :: Monoid m => (a0 -> m) -> Heap a a0 -> m # foldr :: (a0 -> b -> b) -> b -> Heap a a0 -> b # foldr' :: (a0 -> b -> b) -> b -> Heap a a0 -> b # foldl :: (b -> a0 -> b) -> b -> Heap a a0 -> b # foldl' :: (b -> a0 -> b) -> b -> Heap a a0 -> b # foldr1 :: (a0 -> a0 -> a0) -> Heap a a0 -> a0 # foldl1 :: (a0 -> a0 -> a0) -> Heap a a0 -> a0 # toList :: Heap a a0 -> [a0] # null :: Heap a a0 -> Bool # length :: Heap a a0 -> Int # elem :: Eq a0 => a0 -> Heap a a0 -> Bool # maximum :: Ord a0 => Heap a a0 -> a0 # minimum :: Ord a0 => Heap a a0 -> a0 # sum :: Num a0 => Heap a a0 -> a0 # product :: Num a0 => Heap a a0 -> a0 #
Traversable (Heap a) Source #
Instance details Defined in MonusWeightedSearch.Internal.Heap Methods traverse :: Applicative f => (a0 -> f b) -> Heap a a0 -> f (Heap a b) # sequenceA :: Applicative f => Heap a (f a0) -> f (Heap a a0) # mapM :: Monad m => (a0 -> m b) -> Heap a a0 -> m (Heap a b) # sequence :: Monad m => Heap a (m a0) -> m (Heap a a0) #
(Show a, Show b) => Show (Heap a b) Source #
Instance details Defined in MonusWeightedSearch.Internal.Heap Methods showsPrec :: Int -> Heap a b -> ShowS # show :: Heap a b -> String # showList :: [Heap a b] -> ShowS #
Monus a => Semigroup (Heap a b) Source #
Instance details Defined in MonusWeightedSearch.Internal.Heap Methods (<>) :: Heap a b -> Heap a b -> Heap a b # sconcat :: NonEmpty (Heap a b) -> Heap a b # stimes :: Integral b0 => b0 -> Heap a b -> Heap a b #
Monus a => Monoid (Heap a b) Source #
Instance details Defined in MonusWeightedSearch.Internal.Heap Methods mempty :: Heap a b # mappend :: Heap a b -> Heap a b -> Heap a b # mconcat :: [Heap a b] -> Heap a b #

minView :: Monus a => Heap a b -> Maybe ((a, b), Heap a b) Source #

O(log n). Pop the minimum element and its key in the heap, and return it.

singleton :: a -> b -> Heap a b Source #

A singleton heap.

dijkstra :: Ord a => Graph a -> Graph a Source #

An implementation of Dijkstra's algorithm on Graphs.

monusSort :: [Dist] -> [Dist] Source #

Sort a list of Dist.