Data.Heap

Contents

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

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 with inverted order: The maximum will be extracted 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

heapCompare Source

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

data FstMinPolicy Source

Policy type for a (priority, value) MinPrioHeap.

Instances

Ord priority => HeapPolicy FstMinPolicy (priority, value)

data FstMaxPolicy Source

Policy type for a (priority, value) MaxPrioHeap.

Instances

Ord priority => HeapPolicy FstMaxPolicy (priority, value)

Query

null :: Heap p a -> Bool Source

O(1). Is the Heap empty?

isEmpty :: Heap p a -> Bool Source

O(1). Is the Heap empty?

size :: Heap p a -> Int Source

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 Heaps, please consider using the view function instead, it's not partial.

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 Heaps, please consider using the view function instead, it's not partial.

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 Heaps, please consider using the view function instead, it's not partial.

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

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

Builds the union over all given Heaps.

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