heap-0.3.1: Heaps in Haskell

Data.Heap

Contents

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

heapCompareSource

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

data MinPolicy Source

Policy type for a MinHeap.

Instances

data MaxPolicy Source

Policy type for a MaxHeap

Instances

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

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.