Data.Edison.Coll.LeftistHeap
 Portability GHC, Hugs (MPTC and FD) Stability stable Maintainer robdockins AT fastmail DOT fm
 Contents Type of leftist heaps CollX operations Coll operations OrdCollX operations OrdColl operations Documentation
Description

Leftist Heaps

References:

• Chris Okasaki. Purely Functional Data Structures. 1998. Section 3.1.
Synopsis
 data Heap a empty :: Ord a => Heap a singleton :: Ord a => a -> Heap a fromSeq :: (Ord a, Sequence seq) => seq a -> Heap a insert :: Ord a => a -> Heap a -> Heap a insertSeq :: (Ord a, Sequence seq) => seq a -> Heap a -> Heap a union :: Ord a => Heap a -> Heap a -> Heap a unionSeq :: (Ord a, Sequence seq) => seq (Heap a) -> Heap a delete :: Ord a => a -> Heap a -> Heap a deleteAll :: Ord a => a -> Heap a -> Heap a deleteSeq :: (Ord a, Sequence seq) => seq a -> Heap a -> Heap a null :: Ord a => Heap a -> Bool size :: Ord a => Heap a -> Int member :: Ord a => a -> Heap a -> Bool count :: Ord a => a -> Heap a -> Int strict :: Heap a -> Heap a structuralInvariant :: Ord a => Heap a -> Bool toSeq :: (Ord a, Sequence seq) => Heap a -> seq a lookup :: Ord a => a -> Heap a -> a lookupM :: (Ord a, Monad m) => a -> Heap a -> m a lookupAll :: (Ord a, Sequence seq) => a -> Heap a -> seq a lookupWithDefault :: Ord a => a -> a -> Heap a -> a fold :: Ord a => (a -> b -> b) -> b -> Heap a -> b fold' :: Ord a => (a -> b -> b) -> b -> Heap a -> b fold1 :: Ord a => (a -> a -> a) -> Heap a -> a fold1' :: Ord a => (a -> a -> a) -> Heap a -> a filter :: Ord a => (a -> Bool) -> Heap a -> Heap a partition :: Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a) strictWith :: (a -> b) -> Heap a -> Heap a deleteMin :: Ord a => Heap a -> Heap a deleteMax :: Ord a => Heap a -> Heap a unsafeInsertMin :: Ord a => a -> Heap a -> Heap a unsafeInsertMax :: Ord a => a -> Heap a -> Heap a unsafeFromOrdSeq :: (Ord a, Sequence seq) => seq a -> Heap a unsafeAppend :: Ord a => Heap a -> Heap a -> Heap a filterLT :: Ord a => a -> Heap a -> Heap a filterLE :: Ord a => a -> Heap a -> Heap a filterGT :: Ord a => a -> Heap a -> Heap a filterGE :: Ord a => a -> Heap a -> Heap a partitionLT_GE :: Ord a => a -> Heap a -> (Heap a, Heap a) partitionLE_GT :: Ord a => a -> Heap a -> (Heap a, Heap a) partitionLT_GT :: Ord a => a -> Heap a -> (Heap a, Heap a) minView :: (Ord a, Monad m) => Heap a -> m (a, Heap a) minElem :: Ord a => Heap a -> a maxView :: (Ord a, Monad m) => Heap a -> m (a, Heap a) maxElem :: Ord a => Heap a -> a foldr :: Ord a => (a -> b -> b) -> b -> Heap a -> b foldr' :: Ord a => (a -> b -> b) -> b -> Heap a -> b foldl :: Ord a => (b -> a -> b) -> b -> Heap a -> b foldl' :: Ord a => (b -> a -> b) -> b -> Heap a -> b foldr1 :: Ord a => (a -> a -> a) -> Heap a -> a foldr1' :: Ord a => (a -> a -> a) -> Heap a -> a foldl1 :: Ord a => (a -> a -> a) -> Heap a -> a foldl1' :: Ord a => (a -> a -> a) -> Heap a -> a toOrdSeq :: (Ord a, Sequence seq) => Heap a -> seq a unsafeMapMonotonic :: Ord a => (a -> a) -> Heap a -> Heap a
Type of leftist heaps
data Heap a
Instances
 (Ord a, Arbitrary a) => Arbitrary (Heap a) Ord a => Eq (Heap a) Ord a => Monoid (Heap a) Ord a => Ord (Heap a) (Ord a, Read a) => Read (Heap a) (Ord a, Show a) => Show (Heap a) Ord a => Coll (Heap a) a Ord a => CollX (Heap a) a Ord a => OrdColl (Heap a) a Ord a => OrdCollX (Heap a) a
CollX operations
empty :: Ord a => Heap a
singleton :: Ord a => a -> Heap a
fromSeq :: (Ord a, Sequence seq) => seq a -> Heap a
insert :: Ord a => a -> Heap a -> Heap a
insertSeq :: (Ord a, Sequence seq) => seq a -> Heap a -> Heap a
union :: Ord a => Heap a -> Heap a -> Heap a
unionSeq :: (Ord a, Sequence seq) => seq (Heap a) -> Heap a
delete :: Ord a => a -> Heap a -> Heap a
deleteAll :: Ord a => a -> Heap a -> Heap a
deleteSeq :: (Ord a, Sequence seq) => seq a -> Heap a -> Heap a
null :: Ord a => Heap a -> Bool
size :: Ord a => Heap a -> Int
member :: Ord a => a -> Heap a -> Bool
count :: Ord a => a -> Heap a -> Int
strict :: Heap a -> Heap a
structuralInvariant :: Ord a => Heap a -> Bool
Coll operations
toSeq :: (Ord a, Sequence seq) => Heap a -> seq a
lookup :: Ord a => a -> Heap a -> a
lookupM :: (Ord a, Monad m) => a -> Heap a -> m a
lookupAll :: (Ord a, Sequence seq) => a -> Heap a -> seq a
lookupWithDefault :: Ord a => a -> a -> Heap a -> a
fold :: Ord a => (a -> b -> b) -> b -> Heap a -> b
fold' :: Ord a => (a -> b -> b) -> b -> Heap a -> b
fold1 :: Ord a => (a -> a -> a) -> Heap a -> a
fold1' :: Ord a => (a -> a -> a) -> Heap a -> a
filter :: Ord a => (a -> Bool) -> Heap a -> Heap a
partition :: Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
strictWith :: (a -> b) -> Heap a -> Heap a
OrdCollX operations
deleteMin :: Ord a => Heap a -> Heap a
deleteMax :: Ord a => Heap a -> Heap a
unsafeInsertMin :: Ord a => a -> Heap a -> Heap a
unsafeInsertMax :: Ord a => a -> Heap a -> Heap a
unsafeFromOrdSeq :: (Ord a, Sequence seq) => seq a -> Heap a
unsafeAppend :: Ord a => Heap a -> Heap a -> Heap a
filterLT :: Ord a => a -> Heap a -> Heap a
filterLE :: Ord a => a -> Heap a -> Heap a
filterGT :: Ord a => a -> Heap a -> Heap a
filterGE :: Ord a => a -> Heap a -> Heap a
partitionLT_GE :: Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT :: Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT :: Ord a => a -> Heap a -> (Heap a, Heap a)
OrdColl operations
minView :: (Ord a, Monad m) => Heap a -> m (a, Heap a)
minElem :: Ord a => Heap a -> a
maxView :: (Ord a, Monad m) => Heap a -> m (a, Heap a)
maxElem :: Ord a => Heap a -> a
foldr :: Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr' :: Ord a => (a -> b -> b) -> b -> Heap a -> b
foldl :: Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' :: Ord a => (b -> a -> b) -> b -> Heap a -> b
foldr1 :: Ord a => (a -> a -> a) -> Heap a -> a
foldr1' :: Ord a => (a -> a -> a) -> Heap a -> a
foldl1 :: Ord a => (a -> a -> a) -> Heap a -> a
foldl1' :: Ord a => (a -> a -> a) -> Heap a -> a
toOrdSeq :: (Ord a, Sequence seq) => Heap a -> seq a
unsafeMapMonotonic :: Ord a => (a -> a) -> Heap a -> Heap a
Documentation