Data.Heap

Description

A flexible implementation of min-, max- 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 `Heap`s, 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 `(priority, value)` 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 a `HeapPolicy` and let the maintainer know, what's missing.

This module is best imported `qualified` in order to prevent name clashes with other modules.

Synopsis

# Types

## Various heap flavours

data Heap p a Source

The basic `Heap` type.

Instances

 HeapPolicy p a => Eq (Heap p a) HeapPolicy p a => Ord (Heap p a) (HeapPolicy p a, Read a) => Read (Heap p a) Show a => Show (Heap p a) HeapPolicy p a => Monoid (Heap p a)

type MinHeap a = Heap MinPolicy aSource

A `Heap` which will always extract the minimum first.

type MaxHeap a = Heap MaxPolicy aSource

A `Heap` which will always extract the maximum first.

type MinPrioHeap priority value = Heap FstMinPolicy (priority, value)Source

A `Heap` storing priority-value-associations. It only regards the priority for determining the order of elements, the tuple with minimal `fst` value (i. e. priority) will always be the head of the `Heap`.

type MaxPrioHeap priority value = Heap FstMaxPolicy (priority, value)Source

A `Heap` storing priority-value-associations. It only regards the priority for determining the order of elements, the tuple with maximal `fst` value (i. e. priority) will always be the head of the `Heap`.

## Ordering policies

class HeapPolicy p a whereSource

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

Methods

Arguments

 :: p Must not be evaluated. -> a Compared to 3rd parameter. -> a Compared to 2nd parameter. -> Ordering Result of the comparison.

Compare two elements, just like `compare` of the `Ord` class, so this function has to define a mathematical ordering. When using a `HeapPolicy` for a `Heap`, the minimal value (defined by this order) will be the head of the `Heap`.

Instances

 Ord a => HeapPolicy MaxPolicy a Ord a => HeapPolicy MinPolicy a Ord priority => HeapPolicy FstMaxPolicy (priority, value) Ord priority => HeapPolicy FstMinPolicy (priority, value)

data MinPolicy Source

Policy type for a `MinHeap`.

Instances

 Ord a => HeapPolicy MinPolicy a

data MaxPolicy Source

Policy type for a `MaxHeap`.

Instances

 Ord a => HeapPolicy MaxPolicy a

Policy type for a `(priority, value)` `MinPrioHeap`.

Instances

 Ord priority => HeapPolicy FstMinPolicy (priority, value)

Policy type for a `(priority, value)` `MaxPrioHeap`.

Instances

 Ord priority => HeapPolicy FstMaxPolicy (priority, value)

# Query

null :: Heap p a -> BoolSource

O(1). Is the `Heap` empty?

isEmpty :: Heap p a -> BoolSource

O(1). Is the `Heap` empty?

size :: Heap p a -> IntSource

O(1). The number of elements in the `Heap`.

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

O(1). Returns the first item of the `Heap`, according to its `HeapPolicy`.

Warning: This function issues an `error` for empty `Heap`s, please consider using the `view` function instead, it's safe.

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

O(log n). Returns the `Heap` with the `head` removed.

Warning: This function issues an `error` for empty `Heap`s, please consider using the `view` function instead, it's safe.

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

O(log n) for the tail, O(1) for the head. Find the minimum (depending on the `HeapPolicy`) and delete it from the `Heap` (i. e. find head and tail of a heap) if it is not empty. Otherwise, `Nothing` is returned.

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

O(log n). Returns `head` and `tail` of a `Heap`.

Warning: This function issues an `error` for empty `Heap`s, please consider using the `view` function instead, it's safe.

# Construction

empty :: Heap p aSource

O(1). Constructs an empty `Heap`.

singleton :: a -> Heap p aSource

O(1). Create a singleton `Heap`.

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

O(log n). Insert an element in the `Heap`.

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

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

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

Builds the union over all given `Heap`s.

# Filter

filter :: HeapPolicy p a => (a -> Bool) -> Heap p a -> Heap p aSource

Removes all elements from a given `Heap` that do not fulfil the predicate.

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

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

# Subranges

take :: HeapPolicy p a => Int -> Heap p a -> [a]Source

Take the lowest `n` elements in ascending order of the `Heap` (according to the `HeapPolicy`).

drop :: HeapPolicy p a => Int -> Heap p a -> Heap p aSource

Remove the lowest (according to the `HeapPolicy`) `n` elements from the `Heap`.

splitAt :: HeapPolicy p a => Int -> Heap p a -> ([a], Heap p a)Source

`splitAt n h` returns an ascending list of the lowest `n` elements of `h` (according to its `HeapPolicy`) and a `Heap` like `h`, lacking those elements.

takeWhile :: HeapPolicy p a => (a -> Bool) -> Heap p a -> [a]Source

`takeWhile p h` lists the longest prefix of elements in ascending order (according to its `HeapPolicy`) of `h` that satisfy `p`.

dropWhile :: HeapPolicy p a => (a -> Bool) -> Heap p a -> Heap p aSource

`dropWhile p h` removes the longest prefix of elements from `h` that satisfy `p`.

span :: HeapPolicy p a => (a -> Bool) -> Heap p a -> ([a], Heap p a)Source

`span p h` returns the longest prefix of elements in ascending order (according to its `HeapPolicy`) of `h` that satisfy `p` and a `Heap` like `h`, with those elements removed.

break :: HeapPolicy p a => (a -> Bool) -> Heap p a -> ([a], Heap p a)Source

`break p h` returns the longest prefix of elements in ascending order (according to its `HeapPolicy`) of `h` that do not satisfy `p` and a `Heap` like `h`, with those elements removed.

# Conversion

## List

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

Builds a `Heap` from the given elements. Assuming you have a sorted list, you may want to use `fromDescList` or `fromAscList`, they are both faster than this function.

toList :: Heap p a -> [a]Source

O(n). Lists elements of the `Heap` in no specific order.

elems :: Heap p a -> [a]Source

O(n). Lists elements of the `Heap` in no specific order.

## Ordered list

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 its `Ord` instance declaration (if there is one). This function is faster than `fromList` but not as fast as `fromDescList`.

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`).

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

O(n). Create a `Heap` from a descending list. Note that the list has to be descending corresponding to the `HeapPolicy`, not to its `Ord` instance declaration (if there is one). This function is provided, because it is much faster than `fromList` and `fromAscList`.

The precondition is not checked.

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

O(n). Lists the elements on the `Heap` in descending order (corresponding to the `HeapPolicy`). Note that this function is not especially efficient (it is implemented as `reverse . toAscList`), it is just provided as a counterpart of the very efficient `fromDescList` function.