ac-library-hs-0.1.0.0: Data structures and algorithms

Safe Haskell	None
Language	GHC2021

AtCoder.Internal.MinHeap

Contents

Heap
Constructor
Accessors
Accessors
Modifying the heap

Description

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

Synopsis

data Heap s a
new :: (Unbox a, PrimMonad m) => Int -> m (Heap (PrimState m) a)
capacity :: Unbox a => Heap s a -> Int
length :: (Unbox a, PrimMonad m) => Heap (PrimState m) a -> m Int
null :: (Unbox a, PrimMonad m) => Heap (PrimState m) a -> m Bool
clear :: (Unbox a, PrimMonad m) => Heap (PrimState m) a -> m ()
push :: (HasCallStack, Ord a, Unbox a, PrimMonad m) => Heap (PrimState m) a -> a -> m ()
peek :: (Unbox a, PrimMonad m) => Heap (PrimState m) a -> m (Maybe a)
pop :: (HasCallStack, Ord a, Unbox a, PrimMonad m) => Heap (PrimState m) a -> m (Maybe a)
pop_ :: (HasCallStack, Ord a, Unbox a, PrimMonad m) => Heap (PrimState m) a -> m ()

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

Constructor

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

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

Since: 1.0.0

Accessors

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

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

Since: 1.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

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

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

Since: 1.0.0

Accessors

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

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

Since: 1.0.0

Modifying the heap

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

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

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

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

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

Since: 1.0.0