Data.Queue.Indexed.Pairing

Size-indexed pairing heaps.

Documentation

data Pairing n a where

A simple size-indexed pairing heap. In practice, this heap seems to have the best performance.

Inspired by the implementation here, but uses type-level literals, rather than type-level Peano numbers.

Constructors

E :: Pairing 0 a

T :: a -> HVec n a -> Pairing (1 + n) a

Instances

Ord a => MeldableIndexedQueue Pairing a

Methods

merge :: Pairing n a -> Pairing m a -> Pairing (n + m) a

Ord a => IndexedQueue Pairing a

Methods

empty :: Pairing 0 a

minView :: Pairing (1 + n) a -> (a, Pairing n a)

singleton :: a -> Pairing 1 a

insert :: a -> Pairing n a -> Pairing (1 + n) a

minViewMay :: Pairing n a -> ((Nat ~ n) 0 -> b) -> (forall m. (Nat ~ (1 + m)) n => a -> Pairing m a -> b) -> b

NFData a => NFData (Pairing n a)

Methods

rnf :: Pairing n a -> ()

data HVec n a where

A size-indexed vector of pairing heaps.

Constructors

HNil :: HVec 0 a

HCons :: Pairing m a -> HVec n a -> HVec (m + n) a

Instances

NFData a => NFData (HVec n a)

Methods

rnf :: HVec n a -> ()