Data.Heap

Description

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.

Synopsis

# Heap type

data Heap p a Source

The basic `Heap` type.

Instances

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

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

Compare two elements, just like `compare` of the `Ord` class. The first parameter must be ignored by the implementation.

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

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

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.

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

Builds the union over all given `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.

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