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.

This type alias is an abbreviation for a HeapT which uses the HeapItem instance of pol item to organise its elements.

A Heap which will always extract the minimum first.

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 minmal priority will always be extracted 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.

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)

Policy type for a MinHeap.

Policy type for a MaxHeap.

Policy type for a (prio, val) MinPrioHeap.

Policy type for a (prio, val) MaxPrioHeap.

O(1). Is the HeapT empty?

O(1). Is the HeapT empty?

O(1). The total number of elements in the HeapT.

O(1). Construct an empty HeapT.

O(1). Create a singleton HeapT.

O(log n). Insert a single item into the HeapT.

O(log max(n, m)). Form the union of two HeapTs.

Build the union of all given HeapTs.

O(1) for the head, O(log n) for the tail. Find the item with minimal associated priority and remove it from the Heap (i. e. find head and tail of the heap) if it is not empty. Otherwise, Nothing is returned.

O(1). Find the item with minimal associated priority on the Heap (i. e. its head) if it is not empty. Otherwise, Nothing is returned.

O(log n). Remove the item with minimal associated priority and from the Heap (i. e. its tail) if it is not empty. Otherwise, Nothing is returned.

Remove all items from a HeapT not fulfilling a predicate.

Partition the Heap into two. partition p h = (h1, h2): All items in h1 fulfil the predicate p, those in h2 don't. union h1 h2 = h.

Take the first n items from the Heap.

Remove first n items from the Heap.

splitAt n h: Return a list of the first n items of h and h, with those elements removed.

takeWhile p h: List the longest prefix of items in h that satisfy p.

dropWhile p h: Remove the longest prefix of items in h that satisfy p.

span p h: Return the longest prefix of items in h that satisfy p and h, with those elements removed.

break p h: The longest prefix of items in h that do not satisfy p and h, with those elements removed.

O(n log n). Build a Heap from the given items. Assuming you have a sorted list, you probably want to use fromDescList or fromAscList, they are faster than this function.

O(n log n). List all items of the Heap in no specific order.

O(n). Create a Heap from a list providing its items in ascending order of priority (i. e. in the same order they will be removed from the Heap). This function is faster than fromList but not as fast as fromDescList.

The precondition is not checked.

O(n log n). List the items of the Heap in ascending order of priority.

O(n). Create a Heap from a list providing its items in descending order of priority (i. e. they will be removed inversely from the Heap). Prefer this function over fromList and fromAscList, it's faster.

The precondition is not checked.

O(n log n). List the items of the Heap in descending order of priority. Note that this function is not especially efficient (it is implemented in terms of reverse and toAscList), it is provided as a counterpart of the efficient fromDescList function.