| Copyright | (c) 2008-2015 Dan Doel |
|---|---|
| Maintainer | Dan Doel <dan.doel@gmail.com> |
| Stability | Experimental |
| Portability | Non-portable (type operators) |
| Safe Haskell | None |
| Language | Haskell98 |
Data.Vector.Algorithms.Heap
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.
- 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.
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
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.
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.
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
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.
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.
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
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.
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.
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.
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.