Data.Edison.Coll.SkewHeap

Skew heaps.

References:

• Daniel Sleator and Robert Tarjan. "Self-Adjusting Heaps". SIAM Journal on Computing, 15(1):52-69, February 1986.

Type of skew heaps

data Heap a

Instances

Ord a => Eq (Heap a)

Methods

(==) :: Heap a -> Heap a -> Bool

(/=) :: Heap a -> Heap a -> Bool

Ord a => Ord (Heap a)

Methods

compare :: Heap a -> Heap a -> Ordering

(<) :: Heap a -> Heap a -> Bool

(<=) :: Heap a -> Heap a -> Bool

(>) :: Heap a -> Heap a -> Bool

(>=) :: Heap a -> Heap a -> Bool

max :: Heap a -> Heap a -> Heap a

min :: Heap a -> Heap a -> Heap a

(Ord a, Read a) => Read (Heap a)

Methods

readsPrec :: Int -> ReadS (Heap a)

readList :: ReadS [Heap a]

readPrec :: ReadPrec (Heap a)

readListPrec :: ReadPrec [Heap a]

(Ord a, Show a) => Show (Heap a)

Methods

showsPrec :: Int -> Heap a -> ShowS

show :: Heap a -> String

showList :: [Heap a] -> ShowS

Ord a => Semigroup (Heap a)

Methods

(<>) :: Heap a -> Heap a -> Heap a

sconcat :: NonEmpty (Heap a) -> Heap a

stimes :: Integral b => b -> Heap a -> Heap a

Ord a => Monoid (Heap a)

Methods

mempty :: Heap a

mappend :: Heap a -> Heap a -> Heap a

mconcat :: [Heap a] -> Heap a

(Ord a, Arbitrary a) => Arbitrary (Heap a)

Methods

arbitrary :: Gen (Heap a)

shrink :: Heap a -> [Heap a]

(Ord a, CoArbitrary a) => CoArbitrary (Heap a)

Methods

coarbitrary :: Heap a -> Gen b -> Gen b

Ord a => CollX (Heap a) a

Methods

singleton :: a -> Heap a

fromSeq :: Sequence seq => seq a -> Heap a

unionSeq :: Sequence seq => seq (Heap a) -> Heap a

insert :: a -> Heap a -> Heap a

insertSeq :: Sequence seq => seq a -> Heap a -> Heap a

delete :: a -> Heap a -> Heap a

deleteAll :: a -> Heap a -> Heap a

deleteSeq :: Sequence seq => seq a -> Heap a -> Heap a

null :: Heap a -> Bool

size :: Heap a -> Int

member :: a -> Heap a -> Bool

count :: a -> Heap a -> Int

strict :: Heap a -> Heap a

structuralInvariant :: Heap a -> Bool

instanceName :: Heap a -> String

Ord a => OrdCollX (Heap a) a

Methods

deleteMin :: Heap a -> Heap a

deleteMax :: Heap a -> Heap a

unsafeInsertMin :: a -> Heap a -> Heap a

unsafeInsertMax :: a -> Heap a -> Heap a

unsafeFromOrdSeq :: Sequence seq => seq a -> Heap a

unsafeAppend :: Heap a -> Heap a -> Heap a

filterLT :: a -> Heap a -> Heap a

filterLE :: a -> Heap a -> Heap a

filterGT :: a -> Heap a -> Heap a

filterGE :: a -> Heap a -> Heap a

partitionLT_GE :: a -> Heap a -> (Heap a, Heap a)

partitionLE_GT :: a -> Heap a -> (Heap a, Heap a)

partitionLT_GT :: a -> Heap a -> (Heap a, Heap a)

Ord a => Coll (Heap a) a

Methods

toSeq :: Sequence seq => Heap a -> seq a

lookup :: a -> Heap a -> a

lookupM :: Monad m => a -> Heap a -> m a

lookupAll :: Sequence seq => a -> Heap a -> seq a

lookupWithDefault :: a -> a -> Heap a -> a

fold :: (a -> b -> b) -> b -> Heap a -> b

fold' :: (a -> b -> b) -> b -> Heap a -> b

fold1 :: (a -> a -> a) -> Heap a -> a

fold1' :: (a -> a -> a) -> Heap a -> a

filter :: (a -> Bool) -> Heap a -> Heap a

partition :: (a -> Bool) -> Heap a -> (Heap a, Heap a)

strictWith :: (a -> b) -> Heap a -> Heap a

Ord a => OrdColl (Heap a) a

Methods

minView :: Monad m => Heap a -> m (a, Heap a)

minElem :: Heap a -> a

maxView :: Monad m => Heap a -> m (a, Heap a)

maxElem :: Heap a -> a

foldr :: (a -> b -> b) -> b -> Heap a -> b

foldr' :: (a -> b -> b) -> b -> Heap a -> b

foldl :: (b -> a -> b) -> b -> Heap a -> b

foldl' :: (b -> a -> b) -> b -> Heap a -> b

foldr1 :: (a -> a -> a) -> Heap a -> a

foldr1' :: (a -> a -> a) -> Heap a -> a

foldl1 :: (a -> a -> a) -> Heap a -> a

foldl1' :: (a -> a -> a) -> Heap a -> a

toOrdSeq :: Sequence seq => Heap a -> seq a

unsafeMapMonotonic :: (a -> a) -> Heap a -> Heap 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

moduleName :: String