EdisonCore-1.2.1.1: A library of efficent, purely-functional data structures (Core Implementations)Source codeContentsIndex
Data.Edison.Coll.SkewHeap
PortabilityGHC, Hugs (MPTC and FD)
Stabilitystable
Maintainerrobdockins AT fastmail DOT fm
Contents
Type of skew heaps
CollX operations
Coll operations
OrdCollX operations
OrdColl operations
Documentation
Description

Skew heaps.

References:

  • Daniel Sleator and Robert Tarjan. "Self-Adjusting Heaps". SIAM Journal on Computing, 15(1):52-69, February 1986.
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 skew heaps
data Heap a Source
show/hide Instances
Ord a => Eq (Heap a)
Ord a => Ord (Heap a)
(Ord a, Read a) => Read (Heap a)
(Ord a, Show a) => Show (Heap a)
Ord a => Monoid (Heap a)
(Ord a, Arbitrary a) => Arbitrary (Heap a)
Ord a => CollX (Heap a) a
Ord a => OrdCollX (Heap a) a
Ord a => Coll (Heap a) a
Ord a => OrdColl (Heap a) a
CollX operations
empty :: Ord a => Heap aSource
singleton :: Ord a => a -> Heap aSource
fromSeq :: (Ord a, Sequence seq) => seq a -> Heap aSource
insert :: Ord a => a -> Heap a -> Heap aSource
insertSeq :: (Ord a, Sequence seq) => seq a -> Heap a -> Heap aSource
union :: Ord a => Heap a -> Heap a -> Heap aSource
unionSeq :: (Ord a, Sequence seq) => seq (Heap a) -> Heap aSource
delete :: Ord a => a -> Heap a -> Heap aSource
deleteAll :: Ord a => a -> Heap a -> Heap aSource
deleteSeq :: (Ord a, Sequence seq) => seq a -> Heap a -> Heap aSource
null :: Ord a => Heap a -> BoolSource
size :: Ord a => Heap a -> IntSource
member :: Ord a => a -> Heap a -> BoolSource
count :: Ord a => a -> Heap a -> IntSource
strict :: Heap a -> Heap aSource
structuralInvariant :: Ord a => Heap a -> BoolSource
Coll operations
toSeq :: (Ord a, Sequence seq) => Heap a -> seq aSource
lookup :: Ord a => a -> Heap a -> aSource
lookupM :: (Ord a, Monad m) => a -> Heap a -> m aSource
lookupAll :: (Ord a, Sequence seq) => a -> Heap a -> seq aSource
lookupWithDefault :: Ord a => a -> a -> Heap a -> aSource
fold :: Ord a => (a -> b -> b) -> b -> Heap a -> bSource
fold' :: Ord a => (a -> b -> b) -> b -> Heap a -> bSource
fold1 :: Ord a => (a -> a -> a) -> Heap a -> aSource
fold1' :: Ord a => (a -> a -> a) -> Heap a -> aSource
filter :: Ord a => (a -> Bool) -> Heap a -> Heap aSource
partition :: Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)Source
strictWith :: (a -> b) -> Heap a -> Heap aSource
OrdCollX operations
deleteMin :: Ord a => Heap a -> Heap aSource
deleteMax :: Ord a => Heap a -> Heap aSource
unsafeInsertMin :: Ord a => a -> Heap a -> Heap aSource
unsafeInsertMax :: Ord a => a -> Heap a -> Heap aSource
unsafeFromOrdSeq :: (Ord a, Sequence seq) => seq a -> Heap aSource
unsafeAppend :: Ord a => Heap a -> Heap a -> Heap aSource
filterLT :: Ord a => a -> Heap a -> Heap aSource
filterLE :: Ord a => a -> Heap a -> Heap aSource
filterGT :: Ord a => a -> Heap a -> Heap aSource
filterGE :: Ord a => a -> Heap a -> Heap aSource
partitionLT_GE :: Ord a => a -> Heap a -> (Heap a, Heap a)Source
partitionLE_GT :: Ord a => a -> Heap a -> (Heap a, Heap a)Source
partitionLT_GT :: Ord a => a -> Heap a -> (Heap a, Heap a)Source
OrdColl operations
minView :: (Ord a, Monad m) => Heap a -> m (a, Heap a)Source
minElem :: Ord a => Heap a -> aSource
maxView :: (Ord a, Monad m) => Heap a -> m (a, Heap a)Source
maxElem :: Ord a => Heap a -> aSource
foldr :: Ord a => (a -> b -> b) -> b -> Heap a -> bSource
foldr' :: Ord a => (a -> b -> b) -> b -> Heap a -> bSource
foldl :: Ord a => (b -> a -> b) -> b -> Heap a -> bSource
foldl' :: Ord a => (b -> a -> b) -> b -> Heap a -> bSource
foldr1 :: Ord a => (a -> a -> a) -> Heap a -> aSource
foldr1' :: Ord a => (a -> a -> a) -> Heap a -> aSource
foldl1 :: Ord a => (a -> a -> a) -> Heap a -> aSource
foldl1' :: Ord a => (a -> a -> a) -> Heap a -> aSource
toOrdSeq :: (Ord a, Sequence seq) => Heap a -> seq aSource
unsafeMapMonotonic :: Ord a => (a -> a) -> Heap a -> Heap aSource
Documentation
Produced by Haddock version 2.3.0