| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
KMerge.Heap
Description
Mutable heap for k-merge algorithm.
This data-structure represents a min-heap with the root node *removed*. (internally the filling of root value and sifting down is delayed).
Also there isn't *insert* operation, i.e. the heap can only shrink.
Other heap usual heap operations are *create-heap*, *extract-min* and *replace*.
However, as the MutableHeap always represents a heap with its root (minimum value)
extracted, *extract-min* is "fused" to other operations.
Synopsis
- data MutableHeap s a = MH !(PrimVar s Int) !(SmallMutableArray s a)
- newMutableHeap :: forall a m. (PrimMonad m, Ord a) => NonEmpty a -> m (MutableHeap (PrimState m) a, a)
- replaceRoot :: forall a m. (PrimMonad m, Ord a) => MutableHeap (PrimState m) a -> a -> m a
- extract :: forall a m. (PrimMonad m, Ord a) => MutableHeap (PrimState m) a -> m (Maybe a)
Documentation
data MutableHeap s a Source #
Mutable heap for k-merge algorithm.
Constructors
| MH | |
Fields
| |
newMutableHeap :: forall a m. (PrimMonad m, Ord a) => NonEmpty a -> m (MutableHeap (PrimState m) a, a) Source #
Create new heap, and immediately extract its minimum value.
replaceRoot :: forall a m. (PrimMonad m, Ord a) => MutableHeap (PrimState m) a -> a -> m a Source #
Replace the minimum-value, and immediately extract the new minimum value.