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.