vector-algorithms-0.3.2: Efficient algorithms for vector arraysSource codeContentsIndex
Data.Vector.Algorithms.TriHeap
PortabilityNon-portable (type operators)
StabilityExperimental
MaintainerDan Doel <dan.doel@gmail.com>
Contents
Sorting
Selection
Partial sorts
Heap operations
Description
This module implements operations for working with a trinary 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 trinary heap has internal nodes with up to three 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 ()
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 :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()Source
Sorts a portion of an array [l,u) using a custom ordering
Selection
select :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m ()Source
Moves the lowest k elements to the front of the array. The elements will be in no particular order.
selectBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()Source
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 :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()Source
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 :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m ()Source
Moves the lowest k elements to the front of the array, sorted.
partialSortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m ()Source
Moves the lowest k elements (as defined by the comparison) to the front of the array, sorted.
partialSortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()Source
Moves the lowest k elements in the portion [l,u) of the array into positions [l,k+l), sorted.
Heap operations
heapify :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()Source
Constructs a heap in a portion of an array [l, u)
pop :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()Source
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 :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()Source
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 :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()Source
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.
type Comparison e = e -> e -> OrderingSource
A type of comparisons between two values of a given type.
Produced by Haddock version 2.6.0