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

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

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

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

Combine

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.

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.