Data.Heap

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.

Heap type

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.

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

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

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). Finds the minimum (depending on the HeapPolicy) of the Heap.

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.

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

O(log n). Delete the minimum (depending on the HeapPolicy) from the Heap.

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

O(log n). Find the minimum (depending on the HeapPolicy) and delete it from the Heap. This function is undefined for an empty 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.

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

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

Conversion

Lists

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 lists

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

Debugging

check :: HeapPolicy p a => Heap p a -> Bool

Sanity checks for debugging. This includes checking the ranks and the heap and leftist (the left rank is at least the right rank) properties.