Contents Index

Data.Heap Maintainer Stephan Friedrichs

Contents Heap type Query Construction Combine Conversion List Ordered list Debugging

Description

An efficent implementation of min-priority heaps based on the leftist-heaps from Chris Okasakis book "Purely Functional Data Structures", Cambridge University Press, chapter 3.1, 1998.

Synopsis

data Heap a null :: Heap a -> Bool isEmpty :: Heap a -> Bool size :: Heap a -> Int findMin :: Ord a => Heap a -> a empty :: Heap a singleton :: a -> Heap a insert :: Ord a => a -> Heap a -> Heap a deleteMin :: Ord a => Heap a -> Heap a deleteFindMin :: Ord a => Heap a -> (a, Heap a) removeWhile :: Ord a => (a -> Maybe b) -> Heap a -> (Heap a, [b]) union :: Ord a => Heap a -> Heap a -> Heap a unions :: Ord a => [Heap a] -> Heap a fromList :: Ord a => [a] -> Heap a toList :: Heap a -> [a] elems :: Heap a -> [a] fromAscList :: Ord a => [a] -> Heap a toAscList :: Ord a => Heap a -> [a] check :: Ord a => Heap a -> Bool

Heap type

data Heap a

The Heap type. Instances Ord a => Eq (Heap a) Ord a => Monoid (Heap a) Ord a => Ord (Heap a) Show a => Show (Heap a)

Query

null :: Heap a -> Bool

O(1). Is the Heap empty?

isEmpty :: Heap a -> Bool

O(1). Is the Heap empty?

size :: Heap a -> Int

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

findMin :: Ord a => Heap a -> a

O(1). Finds the minimum of the Heap.

Construction

empty :: Heap a

O(1). Constructs an empty Heap.

singleton :: a -> Heap a

O(1). Create a singleton Heap.

insert :: Ord a => a -> Heap a -> Heap a

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

deleteMin :: Ord a => Heap a -> Heap a

O(log n). Delete the minimum from the Heap.

deleteFindMin :: Ord a => Heap a -> (a, Heap a)

O(log n). Find the minimum and delete it from the Heap.

removeWhile :: Ord a => (a -> Maybe b) -> Heap a -> (Heap a, [b])

Removes and returns results as long as the supplied function returns Just.

Combine

union :: Ord a => Heap a -> Heap a -> Heap a

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

unions :: Ord a => [Heap a] -> Heap a

Builds the union over all given Heaps.

Conversion

List

fromList :: Ord a => [a] -> Heap a

Builds a Heap from the given elements. If you have a sorted list, use fromAscList, which is much more efficient.

toList :: Heap a -> [a]

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

elems :: Heap a -> [a]

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

Ordered list

fromAscList :: Ord a => [a] -> Heap a

O(n). Creates a Heap from an ascending list. The precondition is not checked.

toAscList :: Ord a => Heap a -> [a]

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

Debugging

check :: Ord a => Heap 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.

Produced by Haddock version 0.8