An efficent implementation of min-, max- or custom-priority heaps based on the leftist-heaps from Chris Okasaki's book "Purely Functional Data Structures", Cambridge University Press, 1998, chapter 3.1.

If you need a minimum or maximum heap, use `MinHeap`

resp. `MaxHeap`

. If
you want to define a custom order of the heap elements implement a
`HeapPolicy`

.

This module is best imported `qualified`

in order to prevent name clashes
with other modules.

- data Heap p a
- type MinHeap a = Heap MinPolicy a
- type MaxHeap a = Heap MaxPolicy a
- class HeapPolicy p a where
- heapCompare :: p -> a -> a -> Ordering

- data MinPolicy
- data MaxPolicy
- null :: Heap p a -> Bool
- isEmpty :: Heap p a -> Bool
- size :: Num n => Heap p a -> n
- head :: HeapPolicy p a => Heap p a -> a
- empty :: Heap p a
- singleton :: a -> Heap p a
- insert :: HeapPolicy p a => a -> Heap p a -> Heap p a
- deleteHead :: HeapPolicy p a => Heap p a -> Heap p a
- extractHead :: HeapPolicy p a => Heap p a -> (a, Heap p a)
- union :: HeapPolicy p a => Heap p a -> Heap p a -> Heap p a
- unions :: HeapPolicy p a => [Heap p a] -> Heap p a
- fromList :: HeapPolicy p a => [a] -> Heap p a
- toList :: Heap p a -> [a]
- elems :: Heap p a -> [a]
- fromAscList :: HeapPolicy p a => [a] -> Heap p a
- toAscList :: HeapPolicy p a => Heap p a -> [a]
- check :: HeapPolicy p a => Heap p a -> Bool

# Heap type

The basic `Heap`

type.

HeapPolicy p a => Eq (Heap p a) | |

HeapPolicy p a => Ord (Heap p a) | |

Show a => Show (Heap p a) | |

HeapPolicy p a => Monoid (Heap p a) |

type MaxHeap a = Heap MaxPolicy aSource

A `Heap`

with inverted order: The maximum will be extracted first.

class HeapPolicy p a whereSource

The `HeapPolicy`

class defines an order on the elements contained within
a `Heap`

.

heapCompare :: p -> a -> a -> OrderingSource

Ord a => HeapPolicy MaxPolicy a | |

Ord a => HeapPolicy MinPolicy a |

# Query

head :: HeapPolicy p a => Heap p a -> aSource

*O(1)*. Finds the minimum (depending on the `HeapPolicy`

) of the `Heap`

.

# Construction

deleteHead :: HeapPolicy p a => Heap p a -> Heap p aSource

*O(log n)*. Delete the minimum (depending on the `HeapPolicy`

)
from the `Heap`

.

extractHead :: HeapPolicy p a => Heap p a -> (a, Heap p a)Source

*O(log n)*. Find the minimum (depending on the `HeapPolicy`

) and
delete it from the `Heap`

.

# Combine

union :: HeapPolicy p a => Heap p a -> Heap p a -> Heap p aSource

*O(log max(n, m))*. The union of two `Heap`

s.

# Conversion

## Lists

fromList :: HeapPolicy p a => [a] -> Heap p aSource

Builds a `Heap`

from the given elements.
You may want to use `fromAscList`

, if you have a sorted list.

## Ordered lists

fromAscList :: HeapPolicy p a => [a] -> Heap p aSource

*O(n)*. Creates a `Heap`

from an ascending list. Note that the list
has to be ascending corresponding to the `HeapPolicy`

, not to it's
`Ord`

instance declaration (if there is one).
*The precondition is not checked*.

toAscList :: HeapPolicy p a => Heap p a -> [a]Source

*O(n)*. Lists elements of the `Heap`

in ascending order (corresponding
to the `HeapPolicy`

).

# Debugging

check :: HeapPolicy p a => Heap p a -> BoolSource

Sanity checks for debugging. This includes checking the ranks and the heap and leftist (the left rank is at least the right rank) properties.