heaps-0.2: Asymptotically optimal Brodal/Okasaki heaps.

Portability portable experimental ekmett@gmail.com

Data.Heap

Description

An efficient, asymptotically optimal, implementation of a priority queues extended with support for efficient size, and `Data.Foldable`

Note: Since many function names (but not the type name) clash with Prelude names, this module is usually imported `qualified`, e.g.

```  import Data.Heap (Heap)
import qualified Data.Heap as Heap
```

The implementation of `Heap` is based on bootstrapped skew binomial heaps as described by:

All time bounds are worst-case.

Synopsis

# Heap Type

data Heap a Source

A min-heap of values `a`.

Instances

 Typeable1 Heap Foldable Heap Eq (Heap a) (Ord a, Data a) => Data (Heap a) Ord (Heap a) (Ord a, Read a) => Read (Heap a) Show a => Show (Heap a) Monoid (Heap a)

# Entry type

data Entry p a Source

Constructors

 Entry Fieldspriority :: p payload :: a

Instances

 Typeable2 Entry Functor (Entry p) Foldable (Entry p) Traversable (Entry p) Eq p => Eq (Entry p a) (Data p, Data a) => Data (Entry p a) Ord p => Ord (Entry p a) (Read p, Read a) => Read (Entry p a) (Show p, Show a) => Show (Entry p a)

# Basic functions

O(1). The empty heap

``` empty == fromList []
size empty == 0
```

null :: Heap a -> BoolSource

O(1). Is the heap empty?

``` Data.Heap.null empty         == True
Data.Heap.null (singleton 1) == False
```

size :: Heap a -> IntSource

O(1). The number of elements in the heap.

``` size empty == 0
size (singleton 1) == 1
size (fromList [4,1,2]) == 3
```

singleton :: Ord a => a -> Heap aSource

O(1). A heap with a single element

``` singleton 1 == fromList [1]
singleton 1 == insert 1 empty
size (singleton 1) == 1
```

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

O(1). Insert a new value into the heap.

``` insert 2 (fromList [1,3]) == fromList [3,2,1]
insert 5 empty            == singleton 5
size (insert "Item" xs)    == 1 + size xs
```

minimum :: Heap a -> aSource

O(1). Assumes the argument is a non-`null` heap.

``` minimum (fromList [3,1,2]) == 1
```

deleteMin :: Heap a -> Heap aSource

O(log n). Delete the minimum key from the heap and return the resulting heap.

``` deleteMin (fromList [3,1,2]) == fromList [2,3]
```

union :: Heap a -> Heap a -> Heap aSource

O(1). Meld the values from two heaps into one heap.

``` union (fromList [1,3,5]) (fromList [6,4,2]) = fromList [1..6]
union (fromList [1,1,1]) (fromList [1,2,1]) = fromList [1,1,1,1,1,2]
```

uncons :: Ord a => Heap a -> Maybe (a, Heap a)Source

O(1) access to the minimum element. O(log n) access to the remainder of the heap same operation as `viewMin`

``` uncons (fromList [2,1,3]) == Just (1, fromList [3,2])
```

viewMin :: Ord a => Heap a -> Maybe (a, Heap a)Source

Same as `uncons`

# Transformations

mapMonotonic :: Ord b => (a -> b) -> Heap a -> Heap bSource

O(n). Map a monotone increasing function over the heap. Provides a better constant factor for performance than `map`, but no checking is performed that the function provided is monotone increasing. Misuse of this function can cause a Heap to violate the heap property.

``` map (+1) (fromList [1,2,3]) = fromList [2,3,4]
map (*2) (fromList [1,2,3]) = fromList [2,4,6]
```

map :: Ord b => (a -> b) -> Heap a -> Heap bSource

O(n). Map a function over the heap, returning a new heap ordered appropriately for its fresh contents

``` map negate (fromList [3,1,2]) == fromList [-2,-3,-1]
```

# To/From Lists

toUnsortedList :: Heap a -> [a]Source

O(n). Returns the elements in the heap in some arbitrary, very likely unsorted, order.

``` toUnsortedList (fromList [3,1,2]) == [1,3,2]
fromList . toUnsortedList         == id
```

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

O(n). Build a heap from a list of values.

``` size (fromList [1,5,3]) == 3
fromList . toList = id
toList . fromList = sort
```

sort :: Ord a => [a] -> [a]Source

O(n log n). Perform a heap sort

traverse :: (Applicative t, Ord b) => (a -> t b) -> Heap a -> t (Heap b)Source

O(n log n). Traverse the elements of the heap in sorted order and produce a new heap using `Applicative` side-effects.

mapM :: (Monad m, Ord b) => (a -> m b) -> Heap a -> m (Heap b)Source

O(n log n). Traverse the elements of the heap in sorted order and produce a new heap using `Monad`ic side-effects.

concatMap :: Ord b => (a -> Heap b) -> Heap a -> Heap bSource

O(n). Construct heaps from each element in another heap, and union them together.

concatMap (a -> fromList [a,a+1]) (fromList [1,4]) == fromList [1,2,4,5]

# Filtering

filter :: (a -> Bool) -> Heap a -> Heap aSource

O(n). Filter the heap, retaining only values that satisfy the predicate.

``` filter (>'a') (fromList "ab") == singleton 'b'
filter (>'x') (fromList "ab") == empty
filter (<'a') (fromList "ab") == empty
```

partition :: (a -> Bool) -> Heap a -> (Heap a, Heap a)Source

O(n). Partition the heap according to a predicate. The first heap contains all elements that satisfy the predicate, the second all elements that fail the predicate. See also `split`.

``` partition (>'a') (fromList "ab") (singleton 'b', singleton 'a')
```

split :: a -> Heap a -> (Heap a, Heap a, Heap a)Source

O(n). Partition the heap into heaps of the elements that are less than, equal to, and greater than a given value.

``` split 'h' (fromList "hello") == (singleton 'e', singleton 'h', fromList "lol")
```

break :: (a -> Bool) -> Heap a -> (Heap a, Heap a)Source

O(n log n). `break` applied to a predicate `p` and a heap `xs` returns a tuple where the first element is a heap consisting of the longest prefix the least elements of `xs` that do not satisfy p and the second element is the remainder of the elements in the heap.

``` break (\x -> x `mod` 4 == 0) (fromList [3,5,7,12,13,16]) == (fromList [3,5,7], fromList [12,13,16])
```

`break` `p` is equivalent to `span (not . p)`.

span :: (a -> Bool) -> Heap a -> (Heap a, Heap a)Source

O(n log n). `span` applied to a predicate `p` and a heap `xs` returns a tuple where the first element is a heap consisting of the longest prefix the least elements of xs that satisfy `p` and the second element is the remainder of the elements in the heap.

``` span (\x -> x `mod` 4 == 0) (fromList [4,8,12,14,16]) == (fromList [4,8,12],fromList [14,16])
```

`span` `p xs` is equivalent to `(takeWhile p xs, 'dropWhile p xs)`

take :: Int -> Heap a -> Heap aSource

O(n log n). Return a heap consisting of the least `n` elements of a given heap.

``` take 3 (fromList [10,2,4,1,9,8,2]) == fromList [1,2,2]
```

drop :: Int -> Heap a -> Heap aSource

O(n log n). Return a heap consisting of all members of given heap except for the `n` least elements.

splitAt :: Int -> Heap a -> (Heap a, Heap a)Source

O(n log n). Split a heap into two heaps, the first containing the `n` least elements, the latter consisting of all members of the heap except for those elements.

takeWhile :: (a -> Bool) -> Heap a -> Heap aSource

O(n log n). `takeWhile` applied to a predicate `p` and a heap `xs` returns a heap consisting of the longest prefix the least elements of `xs` that satisfy `p`.

``` takeWhile (\x -> x `mod` 4 == 0) (fromList [4,8,12,14,16]) == fromList [4,8,12]
```

dropWhile :: (a -> Bool) -> Heap a -> Heap aSource

O(n log n). `dropWhile` `p xs` returns the suffix of the heap remaining after `takeWhile` `p xs`.

``` dropWhile (\x -> x `mod` 4 == 0) (fromList [4,8,12,14,16]) == fromList [14,16]
```

# Grouping

group :: Heap a -> Heap (Heap a)Source

O(n log n). Group a heap into a heap of heaps, by unioning together duplicates.

``` group (fromList "hello") == fromList [fromList "h", fromList "e", fromList "ll", fromList "o"]
```

groupBy :: (a -> a -> Bool) -> Heap a -> Heap (Heap a)Source

O(n log n). Group using a user supplied function.

nub :: Heap a -> Heap aSource

O(n log n). Remove duplicate entries from the heap.

``` nub (fromList [1,1,2,6,6]) == fromList [1,2,6]
```

# Intersection

intersect :: Heap a -> Heap a -> Heap aSource

O(n log n + m log m). Intersect the values in two heaps, returning the value in the left heap that compares as equal

intersectWith :: Ord b => (a -> a -> b) -> Heap a -> Heap a -> Heap bSource

O(n log n + m log m). Intersect the values in two heaps using a function to generate the elements in the right heap.

# Duplication

replicate :: Ord a => a -> Int -> Heap aSource

O(log n). Create a heap consisting of multiple copies of the same value.

``` replicate 'a' 10 == fromList "aaaaaaaaaa"
```