Heap is:exact
Pairing heap implementation of dictionary
This module implements operations for working with a quaternary heap
stored in an unboxed array. Most heapsorts are defined in terms of a
binary heap, in which each internal node has at most two children. By
contrast, a quaternary heap has internal nodes with up to four
children. This reduces the number of comparisons in a heapsort
slightly, and improves locality (again, slightly) by flattening out
the heap.
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:
All time bounds are worst-case.
A min-heap of values of type a.
With this module, you can investigate the heap representation of
Haskell values, i.e. to investigate sharing and lazy evaluation.
A flexible implementation of min-, max-, min-priority, max-priority
and custom-priority heaps based on the leftist-heaps from Chris
Okasaki's book "Purely Functional Data Structures", Cambridge
University Press, 1998, chapter 3.1.
There are different flavours of
Heaps, each of them following a
different strategy when ordering its elements:
- Choose MinHeap or MaxHeap if you need a simple
minimum or maximum heap (which always keeps the minimum/maximum
element at the head of the Heap).
- If you wish to manually annotate a value with a priority, e. g. an
IO () action with an Int use MinPrioHeap or
MaxPrioHeap. They manage (prio, val) tuples so that
only the priority (and not the value) influences the order of
elements.
- If you still need something different, define a custom order for
the heap elements by implementing an instance of HeapItem and
let the maintainer know what's missing.
All sorts of heaps mentioned above (
MinHeap,
MaxHeap,
MinPrioHeap and
MaxPrioHeap) are built on the same
underlying type:
HeapT prio val. It is a simple
minimum priority heap. The trick is, that you never insert
(prio,
val) pairs directly: You only insert an "external
representation", usually called
item, and an appropriate
HeapItem instance is used to
split the
item to
a
(prio, val) pair. For details refer to the documentation of
HeapItem.
This type alias is an abbreviation for a
HeapT which uses the
HeapItem instance of
pol item to organise its
elements.
Implementation of pairing heaps stored off-heap