heap-0.3.1: Heaps in Haskell

Data.Heap

Description

A flexible 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.

Synopsis

# Heap type

data Heap p a Source

The basic `Heap` type.

Instances

 Foldable (Heap p) 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` 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`.

Methods

Arguments

 :: p Must not be evaluated. -> a Must be compared to 3rd parameter. -> a Must be 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

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

# Query

null :: Heap p a -> BoolSource

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

isEmpty :: Heap p a -> BoolSource

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

size :: Num n => Heap p a -> nSource

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

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

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

tail :: 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`. This function is undefined for an empty `Heap`.

# 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

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

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`, lacking those elements.

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`, lacking those elements.

# Conversion

## List

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.

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