Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.BinaryHeap

Description

The ultra fast binary heap taken from cojna/iota. Thanks!

API

Construction

newMinBinaryHeap, buildMinBinaryHeap
newMaxBinaryHeap, buildMaxBinaryHeap

Operations and views

Reset

clearBH

Synopsis

data BinaryHeap (f :: Type -> Type) s a = BinaryHeap {
- priorityBH :: !(a -> f a)
- intVarsBH :: !(MVector s Int)
- internalVecBH :: !(MVector s a)
}
_sizeBH :: Int
type MinBinaryHeap s a = BinaryHeap Identity s a
type MaxBinaryHeap s a = BinaryHeap Down s a
newBinaryHeap :: (Unbox a, PrimMonad m) => (a -> f a) -> Int -> m (BinaryHeap f (PrimState m) a)
newMinBinaryHeap :: (Unbox a, PrimMonad m) => Int -> m (MinBinaryHeap (PrimState m) a)
newMaxBinaryHeap :: (Unbox a, PrimMonad m) => Int -> m (MaxBinaryHeap (PrimState m) a)
sizeBN :: PrimMonad m => BinaryHeap f (PrimState m) a -> m Int
siftUpBy :: (Unbox a, PrimMonad m) => (a -> a -> Ordering) -> Int -> MVector (PrimState m) a -> m ()
siftDownBy :: (Unbox a, PrimMonad m) => (a -> a -> Ordering) -> Int -> MVector (PrimState m) a -> m ()
heapifyBy :: (Unbox a, PrimMonad m) => (a -> a -> Ordering) -> MVector (PrimState m) a -> m ()
class OrdVia f a where
- compareVia :: (a -> f a) -> a -> a -> Ordering
buildBinaryHeapVia :: (OrdVia f a, Unbox a, PrimMonad m) => (a -> f a) -> Vector a -> m (BinaryHeap f (PrimState m) a)
buildMinBinaryHeap :: (Ord a, Unbox a, PrimMonad m) => Vector a -> m (BinaryHeap Identity (PrimState m) a)
buildMaxBinaryHeap :: (Ord a, Unbox a, PrimMonad m) => Vector a -> m (BinaryHeap Down (PrimState m) a)
unsafeViewBH :: (Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> m a
viewBH :: (Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> m (Maybe a)
insertBH :: (OrdVia f a, Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> a -> m ()
unsafeDeleteBH_ :: (OrdVia f a, Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> m ()
unsafeDeleteBH :: (OrdVia f a, Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> m a
modifyBH :: (OrdVia f a, Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> (a -> a) -> m ()
deleteBH :: (OrdVia f a, Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> m (Maybe a)
clearBH :: PrimMonad m => BinaryHeap f (PrimState m) a -> m ()
unsafeFreezeBH :: (Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> m (Vector a)

Documentation

data BinaryHeap (f :: Type -> Type) s a #

Binary tree backed by a vector.

0-based index

Left child is given as i .<<. 1 + 1. Right child is left child + 1. Parent is (i - 1) .>>. 1.

    0
  1   2
 3 4 5 6

Invariant

Parent value is smaller than or equal to their children.

Constructors

BinaryHeap
Fields priorityBH :: !(a -> f a) Newtype of `OrdVia` intVarsBH :: !(MVector s Int) Stores the size of the heap. internalVecBH :: !(MVector s a) The storage.

_sizeBH :: Int #

type MinBinaryHeap s a = BinaryHeap Identity s a #

type MaxBinaryHeap s a = BinaryHeap Down s a #

newBinaryHeap :: (Unbox a, PrimMonad m) => (a -> f a) -> Int -> m (BinaryHeap f (PrimState m) a) #

newMinBinaryHeap :: (Unbox a, PrimMonad m) => Int -> m (MinBinaryHeap (PrimState m) a) #

newMaxBinaryHeap :: (Unbox a, PrimMonad m) => Int -> m (MaxBinaryHeap (PrimState m) a) #

sizeBN :: PrimMonad m => BinaryHeap f (PrimState m) a -> m Int #

siftUpBy :: (Unbox a, PrimMonad m) => (a -> a -> Ordering) -> Int -> MVector (PrimState m) a -> m () #

\(O(\log N)\) Moves a leaf value upwards order to keep the invariant.

siftDownBy :: (Unbox a, PrimMonad m) => (a -> a -> Ordering) -> Int -> MVector (PrimState m) a -> m () #

\(O(\log N)\) Moves a parent vertex downwards in order to keep the invariant.

heapifyBy :: (Unbox a, PrimMonad m) => (a -> a -> Ordering) -> MVector (PrimState m) a -> m () #

\(O(N \log N)\) Sorts a vector as a heap.

class OrdVia f a where #

Compare via a newtype.

Methods

compareVia :: (a -> f a) -> a -> a -> Ordering #

Instances

Instances details

Ord a => OrdVia Identity a #
Instance details Defined in Data.BinaryHeap Methods compareVia :: (a -> Identity a) -> a -> a -> Ordering #
Ord a => OrdVia Down a #
Instance details Defined in Data.BinaryHeap Methods compareVia :: (a -> Down a) -> a -> a -> Ordering #

buildBinaryHeapVia :: (OrdVia f a, Unbox a, PrimMonad m) => (a -> f a) -> Vector a -> m (BinaryHeap f (PrimState m) a) #

\(O(N \log N)\) Creates a binary heap with a newtype comparator and a vector.

buildMinBinaryHeap :: (Ord a, Unbox a, PrimMonad m) => Vector a -> m (BinaryHeap Identity (PrimState m) a) #

\(O(N \log N)\) Creates a BinaryHeap from a vector.

buildMaxBinaryHeap :: (Ord a, Unbox a, PrimMonad m) => Vector a -> m (BinaryHeap Down (PrimState m) a) #

\(O(N \log N)\) Creates a BinaryHeap from a vector.

unsafeViewBH :: (Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> m a #

\(O(1)\) Reads the top node. Returns an unknown value when the heap is emtpy.

viewBH :: (Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> m (Maybe a) #

\(O(1)\) Reads the top nodes.

insertBH :: (OrdVia f a, Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> a -> m () #

\(O(\log N)\) Inserts a value as a leaf and sorts upwards.

unsafeDeleteBH_ :: (OrdVia f a, Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> m () #

\(O(\log N)\) Deletes the top node. Returns nothing.

unsafeDeleteBH :: (OrdVia f a, Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> m a #

\(O(\log N)\) Deletes and returns the top node.

modifyBH :: (OrdVia f a, Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> (a -> a) -> m () #

\(O(\log N)\) Modifies the top node of the heap.

deleteBH :: (OrdVia f a, Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> m (Maybe a) #

\(O(\log N)\) Deletes and returns the top node.

clearBH :: PrimMonad m => BinaryHeap f (PrimState m) a -> m () #

\(O(1)\) Clears the heap.

unsafeFreezeBH :: (Unbox a, PrimMonad m) => BinaryHeap f (PrimState m) a -> m (Vector a) #