halg-heaps-0.1.0.0: Various heap structures
Safe HaskellNone
LanguageHaskell2010

Data.Heap.Pairing

Synopsis

Documentation

data Pairing a Source #

Ephemeral heap, implemented as a Pairing Pairing.

Instances

Instances details
Foldable Pairing Source #

Folds item in an increasing order

Instance details

Defined in Data.Heap.Pairing

Methods

fold :: Monoid m => Pairing m -> m #

foldMap :: Monoid m => (a -> m) -> Pairing a -> m #

foldMap' :: Monoid m => (a -> m) -> Pairing a -> m #

foldr :: (a -> b -> b) -> b -> Pairing a -> b #

foldr' :: (a -> b -> b) -> b -> Pairing a -> b #

foldl :: (b -> a -> b) -> b -> Pairing a -> b #

foldl' :: (b -> a -> b) -> b -> Pairing a -> b #

foldr1 :: (a -> a -> a) -> Pairing a -> a #

foldl1 :: (a -> a -> a) -> Pairing a -> a #

toList :: Pairing a -> [a] #

null :: Pairing a -> Bool #

length :: Pairing a -> Int #

elem :: Eq a => a -> Pairing a -> Bool #

maximum :: Ord a => Pairing a -> a #

minimum :: Ord a => Pairing a -> a #

sum :: Num a => Pairing a -> a #

product :: Num a => Pairing a -> a #

Heap Pairing Source # 
Instance details

Defined in Data.Heap.Pairing

Methods

empty :: Ord a => Pairing a Source #

null :: Ord a => Pairing a -> Bool Source #

insert :: Ord a => a -> Pairing a -> Pairing a Source #

merge :: Ord a => Pairing a -> Pairing a -> Pairing a Source #

findMin :: Ord a => Pairing a -> Maybe a Source #

deleteMin :: Ord a => Pairing a -> Maybe (Pairing a) Source #

singleton :: Ord a => a -> Pairing a Source #

viewMin :: Ord a => Pairing a -> Maybe (a, Pairing a) Source #

fromList :: Ord a => [a] -> Pairing a Source #

toList :: Ord a => Pairing a -> [a] Source #

span :: Ord a => (a -> Bool) -> Pairing a -> (Pairing a, Pairing a) Source #

Eq (Pairing a) Source # 
Instance details

Defined in Data.Heap.Pairing

Methods

(==) :: Pairing a -> Pairing a -> Bool #

(/=) :: Pairing a -> Pairing a -> Bool #

Ord (Pairing a) Source # 
Instance details

Defined in Data.Heap.Pairing

Methods

compare :: Pairing a -> Pairing a -> Ordering #

(<) :: Pairing a -> Pairing a -> Bool #

(<=) :: Pairing a -> Pairing a -> Bool #

(>) :: Pairing a -> Pairing a -> Bool #

(>=) :: Pairing a -> Pairing a -> Bool #

max :: Pairing a -> Pairing a -> Pairing a #

min :: Pairing a -> Pairing a -> Pairing a #

Semigroup (Pairing a) Source # 
Instance details

Defined in Data.Heap.Pairing

Methods

(<>) :: Pairing a -> Pairing a -> Pairing a #

sconcat :: NonEmpty (Pairing a) -> Pairing a #

stimes :: Integral b => b -> Pairing a -> Pairing a #

Monoid (Pairing a) Source # 
Instance details

Defined in Data.Heap.Pairing

Methods

mempty :: Pairing a #

mappend :: Pairing a -> Pairing a -> Pairing a #

mconcat :: [Pairing a] -> Pairing a #

Basic Operations

singleton :: Ord a => a -> Pairing a Source #

O(1), amortised and worst

fromList :: Ord a => [a] -> Pairing a Source #

insert :: Ord a => a -> Pairing a -> Pairing a Source #

O(1), both amortised and worst, insert an element into a heap.

merge :: Pairing a -> Pairing a -> Pairing a Source #

O(1), both amortised and worst, merges two heaps.

union :: Pairing a -> Pairing a -> Pairing a Source #

Synonym for merge.

mapMonotonic :: Ord a => (t -> a) -> Pairing t -> Pairing a Source #

Query

findMin :: Pairing a -> Maybe a Source #

O(1), both amortised and worst, find the minimum element.

deleteMin :: Pairing a -> Maybe (Pairing a) Source #

O(log n) amortised and O(n) worst, removes the least element and returns remainder.

viewMin :: Pairing a -> Maybe (a, Pairing a) Source #

O(1), amortised and worst, for the least element; O(log n) amortised and O(n) worst for the remainder.

uncons :: Ord a => Pairing a -> Maybe (a, Pairing a) Source #

Synonym for viewMin.

span :: (a -> Bool) -> Pairing a -> (Pairing a, Pairing a) Source #

O(n log n), amortised, and O(n^2) worst.