Heap package:heap

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.

Heaps in Haskell A flexible Haskell implementation of minimum, maximum, minimum-priority, maximum-priority and custom-ordered heaps.

HeapItem pol item is a type class for items that can be stored in a HeapT. A raw HeapT prio val only provides a minimum priority heap (i. e. val doesn't influence the ordering of elements and the pair with minimal prio will be extracted first, see HeapT documentation). The job of this class is to translate between arbitrary items and priority-value pairs (Prio pol item, Val pol item), depending on the policy pol to be used. This way, we are able to use HeapT not only as MinPrioHeap, but also as MinHeap, MaxHeap, MaxPrioHeap or a custom implementation. In short: The job of this class is to deconstruct arbitrary items into a (prio, val) pairs that can be handled by a minimum priority HeapT. Example: Consider you want to use HeapT prio val as a MaxHeap a. You would have to invert the order of a (e. g. by introducing newtype InvOrd a = InvOrd a along with an apropriate Ord instance for it) and then use a type MaxHeap a = HeapT (InvOrd a) (). You'd also have to translate every x to (InvOrd x, ()) before insertion and back after removal in order to retrieve your original type a. This functionality is provided by the HeapItem class. In the above example, you'd use a MaxHeap. The according instance declaration is of course already provided and looks like this (simplified): @data MaxPolicy instance (Ord a) => HeapItem MaxPolicy a where newtype Prio MaxPolicy a = MaxP a deriving (Eq) type Val MaxPolicy a = () split x = (MaxP x, ()) merge (MaxP x, _) = x instance (Ord a) => Ord (Prio MaxPolicy a) where compare (MaxP x) (MaxP y) = compare y x @ MaxPolicy is a phantom type describing which HeapItem instance is actually meant (e. g. we have to distinguish between MinHeap and MaxHeap, which is done via MinPolicy and MaxPolicy, respectively) and MaxP inverts the ordering of a, so that the maximum will be on top of the HeapT. The conversion functions split and merge have to make sure that

1. forall p v. split (merge (p, v)) == (p, v) (merge and split don't remove, add or alter anything)
2. forall p v f. fst (split (merge (p, f v)) == fst (split (merge (p, v))) (modifying the associated value v doesn't alter the priority p)

The basic heap type. It stores priority-value pairs (prio, val) and always keeps the pair with minimal priority on top. The value associated to the priority does not have any influence on the ordering of elements.

A Heap which will always extract the maximum first.

A Heap storing priority-value pairs (prio, val). The order of elements is solely determined by the priority prio, the value val has no influence. The priority-value pair with maximum priority will always be extracted first.

A Heap which will always extract the minimum first.

A Heap storing priority-value pairs (prio, val). The order of elements is solely determined by the priority prio, the value val has no influence. The priority-value pair with minmal priority will always be extracted first.