Safe Haskell | None |
---|---|
Language | Haskell2010 |
Simple binomial heaps, with a statically-enforced shape.
Documentation
A binomial heap, where the sizes of the nodes are enforced in the types.
The implementation is based on:
- Hinze, Ralf. “Functional Pearls: Explaining Binomial Heaps.” Journal of Functional Programming 9, no. 1 (January 1999): 93–104. doi:10.1017/S0956796899003317.
- Wasserman, Louis. “Playing with Priority Queues.” The Monad.Reader, May 12, 2010.
It is a list of binomial trees, equivalent to a binary number (stored least-significant-bit first).
Nil | The empty heap |
Skip (Binomial (S rk) a) | Skip a child tree (equivalent to a zero in the binary representation of the data structure). |
(:-) !(Tree rk a) (Binomial (S rk) a) infixr 5 | A child tree. Equivalent to a one in the binary representation. |
Functor (Binomial rk) Source # | |
Foldable (Binomial rk) Source # | |
Traversable (Binomial rk) Source # | |
Generic1 (Binomial n) Source # | |
Ord a => MeldableQueue (Binomial Z) a Source # | |
Ord a => Queue (Binomial Z) a Source # | |
Ord a => Eq (Binomial Z a) Source # | |
Ord a => Ord (Binomial Z a) Source # | |
(Read a, Ord a) => Read (Binomial Z a) Source # | |
(Show a, Ord a) => Show (Binomial Z a) Source # | |
Generic (Binomial n a) Source # | |
Ord a => Monoid (Binomial rk a) Source # | |
NFData a => NFData (Binomial rk a) Source # | |
type Rep1 (Binomial n) Source # | |
type Rep (Binomial n a) Source # | |
A list of binomial trees, indexed by their sizes in ascending order.
A rose tree, where the children are indexed.