Copyright	(c) 2008-2015 Dan Doel
Maintainer	Dan Doel <dan.doel@gmail.com>
Stability	Experimental
Portability	Non-portable (type operators)
Safe Haskell	None
Language	Haskell2010

Data.Vector.Algorithms.Heap

Contents

Sorting
Selection
Partial sorts
Heap operations

Description

This module implements operations for working with a quaternary heap stored in an unboxed array. Most heapsorts are defined in terms of a binary heap, in which each internal node has at most two children. By contrast, a quaternary heap has internal nodes with up to four children. This reduces the number of comparisons in a heapsort slightly, and improves locality (again, slightly) by flattening out the heap.

Synopsis

sort :: ( PrimMonad m, MVector v e, Ord e) => v ( PrimState m) e -> m ()
sortBy :: ( PrimMonad m, MVector v e) => Comparison e -> v ( PrimState m) e -> m ()
sortByBounds :: ( PrimMonad m, MVector v e) => Comparison e -> v ( PrimState m) e -> Int -> Int -> m ()
select :: ( PrimMonad m, MVector v e, Ord e) => v ( PrimState m) e -> Int -> m ()
selectBy :: ( PrimMonad m, MVector v e) => Comparison e -> v ( PrimState m) e -> Int -> m ()
selectByBounds :: ( PrimMonad m, MVector v e) => Comparison e -> v ( PrimState m) e -> Int -> Int -> Int -> m ()
partialSort :: ( PrimMonad m, MVector v e, Ord e) => v ( PrimState m) e -> Int -> m ()
partialSortBy :: ( PrimMonad m, MVector v e) => Comparison e -> v ( PrimState m) e -> Int -> m ()
partialSortByBounds :: ( PrimMonad m, MVector v e) => Comparison e -> v ( PrimState m) e -> Int -> Int -> Int -> m ()
heapify :: ( PrimMonad m, MVector v e) => Comparison e -> v ( PrimState m) e -> Int -> Int -> m ()
pop :: ( PrimMonad m, MVector v e) => Comparison e -> v ( PrimState m) e -> Int -> Int -> m ()
popTo :: ( PrimMonad m, MVector v e) => Comparison e -> v ( PrimState m) e -> Int -> Int -> Int -> m ()
sortHeap :: ( PrimMonad m, MVector v e) => Comparison e -> v ( PrimState m) e -> Int -> Int -> Int -> m ()
heapInsert :: ( PrimMonad m, MVector v e) => Comparison e -> v ( PrimState m) e -> Int -> Int -> e -> m ()
type Comparison e = e -> e -> Ordering

Sorting

sort :: ( PrimMonad m, MVector v e, Ord e) => v ( PrimState m) e -> m () Source #

Sorts an entire array using the default ordering.

sortBy :: ( PrimMonad m, MVector v e) => Comparison e -> v ( PrimState m) e -> m () Source #

Sorts an entire array using a custom ordering.

sortByBounds Source #

Arguments

:: ( PrimMonad m, MVector v e)
=> Comparison e
-> v ( PrimState m) e
-> Int	lower index, l
-> Int	upper index, u
-> m ()

Sorts a portion of an array [l,u) using a custom ordering

Selection

select Source #

Arguments

:: ( PrimMonad m, MVector v e, Ord e)
=> v ( PrimState m) e
-> Int	number of elements to select, k
-> m ()

Moves the lowest k elements to the front of the array. The elements will be in no particular order.

selectBy Source #

Arguments

:: ( PrimMonad m, MVector v e)
=> Comparison e
-> v ( PrimState m) e
-> Int	number of elements to select, k
-> m ()

Moves the lowest (as defined by the comparison) k elements to the front of the array. The elements will be in no particular order.

selectByBounds Source #

Arguments

:: ( PrimMonad m, MVector v e)
=> Comparison e
-> v ( PrimState m) e
-> Int	number of elements to select, k
-> Int	lower index, l
-> Int	upper index, u
-> m ()

Moves the lowest k elements in the portion [l,u) of the array into the positions [l,k+l). The elements will be in no particular order.

Partial sorts

partialSort Source #

Arguments

:: ( PrimMonad m, MVector v e, Ord e)
=> v ( PrimState m) e
-> Int	number of elements to sort, k
-> m ()

Moves the lowest k elements to the front of the array, sorted.

The remaining values of the array will be in no particular order.

partialSortBy Source #

Arguments

:: ( PrimMonad m, MVector v e)
=> Comparison e
-> v ( PrimState m) e
-> Int	number of elements to sort, k
-> m ()

Moves the lowest k elements (as defined by the comparison) to the front of the array, sorted.

The remaining values of the array will be in no particular order.

partialSortByBounds Source #

Arguments

:: ( PrimMonad m, MVector v e)
=> Comparison e
-> v ( PrimState m) e
-> Int	number of elements to sort, k
-> Int	lower index, l
-> Int	upper index, u
-> m ()

Moves the lowest k elements in the portion [l,u) of the array into positions [l,k+l), sorted.

The remaining values in [l,u) will be in no particular order. Values outside the range [l,u) will be unaffected.

Heap operations

heapify Source #

Arguments

:: ( PrimMonad m, MVector v e)
=> Comparison e
-> v ( PrimState m) e
-> Int	lower index, l
-> Int	upper index, u
-> m ()

Constructs a heap in a portion of an array [l, u), using the values therein.

Note: heapify is more efficient than constructing a heap by repeated insertion. Repeated insertion has complexity O(n*log n) while heapify is able to construct a heap in O(n), where n is the number of elements in the heap.

pop Source #

Arguments

:: ( PrimMonad m, MVector v e)
=> Comparison e
-> v ( PrimState m) e
-> Int	lower heap index, l
-> Int	upper heap index, u
-> m ()

Given a heap stored in a portion of an array [l,u), swaps the top of the heap with the element at u and rebuilds the heap.

popTo Source #

Arguments

:: ( PrimMonad m, MVector v e)
=> Comparison e
-> v ( PrimState m) e
-> Int	lower heap index, l
-> Int	upper heap index, u
-> Int	index to pop to, t
-> m ()

Given a heap stored in a portion of an array [l,u) swaps the top of the heap with the element at position t, and rebuilds the heap.

sortHeap Source #

Arguments

:: ( PrimMonad m, MVector v e)
=> Comparison e
-> v ( PrimState m) e
-> Int	lower heap index, l
-> Int	lower bound of final sorted portion, m
-> Int	upper heap index, u
-> m ()

Given a heap stored in a portion of an array [l,u), sorts the highest values into [m,u). The elements in [l,m) are not in any particular order.

heapInsert Source #

Arguments

:: ( PrimMonad m, MVector v e)
=> Comparison e
-> v ( PrimState m) e
-> Int	lower heap index, l
-> Int	upper heap index, u
-> e	element to be inserted, e
-> m ()

Given a heap stored in a portion of an array [l,u) and an element e, inserts the element into the heap, resulting in a heap in [l,u].

Note: it is best to only use this operation when incremental construction of a heap is required. heapify is capable of building a heap in O(n) time, while repeated insertion takes O(n*log n) time.

type Comparison e = e -> e -> Ordering Source #

A type of comparisons between two values of a given type.