Data.Heap

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

Types

Various heap flavours

data Heap p a

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 a

A Heap which will always extract the minimum first.

type MaxHeap a = Heap MaxPolicy a

A Heap with inverted order: The maximum will be extracted first.

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

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)

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 where

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

Methods

heapCompare

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

Ord priority => HeapPolicy FstMaxPolicy (priority, value)

Ord priority => HeapPolicy FstMinPolicy (priority, value)

data MinPolicy

Policy type for a MinHeap.

Instances

Ord a => HeapPolicy MinPolicy a

data MaxPolicy

Policy type for a MaxHeap.

Instances

Ord a => HeapPolicy MaxPolicy a

data FstMinPolicy

Policy type for a (priority, value) MinPrioHeap.

Instances

Ord priority => HeapPolicy FstMinPolicy (priority, value)

data FstMaxPolicy

Policy type for a (priority, value) MaxPrioHeap.

Instances

Ord priority => HeapPolicy FstMaxPolicy (priority, value)

Query

null :: Heap p a -> Bool

O(1). Is the Heap empty?

isEmpty :: Heap p a -> Bool

O(1). Is the Heap empty?

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

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

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

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

Warning: This function issues an error for empty Heaps, please consider using the view function instead, it's not partial.

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

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

Warning: This function issues an error for empty Heaps, please consider using the view function instead, it's not partial.

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

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)

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

Warning: This function issues an error for empty Heaps, please consider using the view function instead, it's not partial.

Construction

empty :: Heap p a

O(1). Constructs an empty Heap.

singleton :: a -> Heap p a

O(1). Create a singleton Heap.

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

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

Union

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

O(log max(n, m)). The union of two Heaps.

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

Builds the union over all given Heaps.

Filter

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

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)

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]

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 a

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

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

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]

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 a

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)

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)

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 a

Builds a Heap from the given elements. You may want to use fromAscList, if you have a sorted list.

toList :: Heap p a -> [a]

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

elems :: Heap p a -> [a]

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

Ordered list

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

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]

O(n). Lists elements of the Heap in ascending order (corresponding to the HeapPolicy).