AtCoder.Internal.MinHeap

Minimum binary heap. Mutable and fixed-sized.

https://en.wikipedia.org/wiki/Binary_heap

Example

>>> import AtCoder.Internal.MinHeap qualified as MH
>>> heap <- MH.new @Int 4
>>> MH.capacity heap
4

>>> MH.push heap 10
>>> MH.push heap 0
>>> MH.push heap 5
>>> MH.length heap -- [0, 5, 10]
3

>>> MH.pop heap    -- [5, 10]
Just 0

>>> MH.peek heap   -- [5, 10]
Just 5

>>> MH.pop heap    -- [10]
Just 5

>>> MH.clear heap  -- []
>>> MH.null heap
True

Since: 1.0.0.0

Heap

data Heap s a

Minimum binary heap. Mutable and fixed-sized.

Indices are zero-based.

    0
  1   2
 3 4 5 6

INVARIANT (min heap): child values are bigger than or equal to their parent value.

Since: 1.0.0.0

Constructors

new :: (Unbox a, PrimMonad m) => Int -> m (Heap (PrimState m) a)

\(O(n)\) Creates a Heap with capacity \(n\).

Since: 1.0.0.0

Metadata

capacity :: Unbox a => Heap s a -> Int

\(O(1)\) Returns the maximum number of elements in the heap.

Since: 1.0.0.0

length :: (Unbox a, PrimMonad m) => Heap (PrimState m) a -> m Int

\(O(1)\) Returns the number of elements in the heap.

Since: 1.0.0.0

null :: (Unbox a, PrimMonad m) => Heap (PrimState m) a -> m Bool

\(O(1)\) Returns True if the heap is empty.

Since: 1.0.0.0

Reset

clear :: (Unbox a, PrimMonad m) => Heap (PrimState m) a -> m ()

\(O(1)\) Sets the length to zero.

Since: 1.0.0.0

Pushpoppeek

push :: (HasCallStack, Ord a, Unbox a, PrimMonad m) => Heap (PrimState m) a -> a -> m ()

\(O(\log n)\) Inserts an element to the heap.

Since: 1.0.0.0

pop :: (HasCallStack, Ord a, Unbox a, PrimMonad m) => Heap (PrimState m) a -> m (Maybe a)

\(O(\log n)\) Removes the last element from the heap and returns it, or Nothing if it is empty.

Since: 1.0.0.0

pop_ :: (HasCallStack, Ord a, Unbox a, PrimMonad m) => Heap (PrimState m) a -> m ()

\(O(\log n)\) pop with the return value discarded.

Since: 1.0.0.0

peek :: (Unbox a, PrimMonad m) => Heap (PrimState m) a -> m (Maybe a)

\(O(1)\) Returns the smallest value in the heap, or Nothing if it is empty.

Since: 1.0.0.0