Heap package:heaps

An efficient, asymptotically optimal, implementation of a priority queues extended with support for efficient size, and Foldable Note: Since many function names (but not the type name) clash with Prelude names, this module is usually imported qualified, e.g.

import Data.Heap (Heap)
import qualified Data.Heap as Heap

The implementation of Heap is based on bootstrapped skew binomial heaps as described by:

G. Brodal and C. Okasaki , "Optimal Purely Functional Priority Queues", Journal of Functional Programming 6:839-857 (1996)

All time bounds are worst-case.

data Heap a

heaps Data.Heap

A min-heap of values of type a.

package heaps

Uses

Asymptotically optimal Brodal/Okasaki heaps. Asymptotically optimal Brodal/Okasaki bootstrapped skew-binomial heaps from the paper "Optimal Purely Functional Priority Queues", extended with a Foldable interface.