Portability | GHC, Hugs (MPTC and FD) |
---|---|

Stability | stable |

Maintainer | robdockins AT fastmail DOT fm |

Safe Haskell | None |

Splay heaps.

If `minElem`

is called frequently, then SplayHeap should
be used in conjunction with Data.Edison.Coll.MinHeap.

*References:*

- Chris Okasaki.
*Purely Functional Data Structures*. 1998. Section 5.4.

- data Heap a
- empty :: Heap a
- singleton :: a -> Heap a
- fromSeq :: (Ord a, Sequence s) => s a -> Heap a
- insert :: Ord a => a -> Heap a -> Heap a
- insertSeq :: (Ord a, Sequence s) => s a -> Heap a -> Heap a
- union :: Ord a => Heap a -> Heap a -> Heap a
- unionSeq :: (Ord a, Sequence s) => s (Heap a) -> Heap a
- delete :: Ord a => a -> Heap a -> Heap a
- deleteAll :: Ord a => a -> Heap a -> Heap a
- deleteSeq :: (Ord a, Sequence s) => s a -> Heap a -> Heap a
- null :: Heap a -> Bool
- size :: 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 s) => Heap a -> s a
- lookup :: Ord a => a -> Heap a -> a
- lookupM :: (Ord a, Monad m) => a -> Heap a -> m a
- lookupAll :: (Ord a, Sequence s) => a -> Heap a -> s 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 s) => s 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 s) => Heap a -> s a
- unsafeMapMonotonic :: (a -> b) -> Heap a -> Heap b
- moduleName :: String

# Type of splay heaps

Ord a => Eq (Heap 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, Arbitrary a) => Arbitrary (Heap a) | |

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

Ord a => Monoid (Heap a) | |

(Eq a, Monoid (Heap a), Ord a) => CollX (Heap a) a | |

(CollX (Heap a) a, Ord a) => OrdCollX (Heap a) a | |

(CollX (Heap a) a, Ord a) => Coll (Heap a) a | |

(Coll (Heap a) a, OrdCollX (Heap a) a, Ord a) => OrdColl (Heap a) a |

# CollX operations

structuralInvariant :: Ord a => Heap a -> BoolSource

# Coll operations

lookupWithDefault :: Ord a => a -> a -> Heap a -> aSource

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

# OrdCollX operations

unsafeInsertMin :: Ord a => a -> Heap a -> Heap aSource

unsafeInsertMax :: Ord a => a -> Heap a -> Heap aSource

unsafeFromOrdSeq :: (Ord a, Sequence s) => s a -> Heap aSource

# OrdColl operations

unsafeMapMonotonic :: (a -> b) -> Heap a -> Heap bSource