Portability | non-portable |
---|---|

Stability | experimental |

Maintainer | Edward Kmett <ekmett@gmail.com> |

Safe Haskell | None |

Bootstrapped *catenable* non-empty pairing heaps as described in

https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/part-5

- data Heap a = Heap !Key a [Heap a] [Heap a] [Heap a]
- fby :: Heap a -> Heap a -> Heap a
- mix :: Heap a -> Heap a -> Heap a
- singleton :: Key -> a -> Heap a
- head :: Heap a -> (Key, a)
- tail :: Heap a -> Maybe (Heap a)
- fromList :: [(Key, a)] -> Heap a
- fromAscList :: [(Key, a)] -> Heap a
- streamHeapWith :: Monad m => (a -> a -> a) -> Maybe (Heap a) -> Stream m (Key, a)
- streamHeapWith0 :: Monad m => (a -> a -> Maybe a) -> Maybe (Heap a) -> Stream m (Key, a)

# Documentation

Bootstrapped catenable non-empty pairing heaps

fby :: Heap a -> Heap a -> Heap aSource

Append two heaps where we know every key in the first occurs before every key in the second

`>>>`

(Key 1 1,1)`head $ singleton (Key 1 1) 1 `fby` singleton (Key 2 2) 2`

mix :: Heap a -> Heap a -> Heap aSource

Interleave two heaps making a new `Heap`

`>>>`

(Key 1 1,1)`head $ singleton (Key 1 1) 1 `mix` singleton (Key 2 2) 2`

fromAscList :: [(Key, a)] -> Heap aSource

Build a `Heap`

from an list of elements that must be in strictly ascending Morton order.