| EdisonCore-1.2.1: A library of efficient, purely-functional data structures (Core Implementations) | Contents | Index |
|
Data.Edison.Coll.SkewHeap | Portability | GHC, Hugs (MPTC and FD) | Stability | stable | Maintainer | robdockins AT fastmail DOT fm |
|
|
|
|
|
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 |
Instances | |
|
|
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
|
|
Produced by Haddock version 0.8 |