heapContext
Unstable in-place sort. O(n*log(n)) best case, worst case and average case.
O(1) memory (no allocator required).
context must have methods swap and lessThan,
which each take 2 usize parameters indicating the index of an item.
Sorts in ascending order with respect to lessThan.
Function parameters
Parameters
- a:usize
- b:usize
- context:anytype
Type definitions in this namespace
Types
Functions in this namespace
Functions
- insertion
- Stable in-place sort.
- insertionContext
- Stable in-place sort.
- heap
- Unstable in-place sort.
- heapContext
- Unstable in-place sort.
- asc
- Use to generate a comparator function for a given type.
- desc
- Use to generate a comparator function for a given type.
- binarySearch
- Returns the index of an element in `items` returning `.eq` when given to `compareFn`.
- lowerBound
- Returns the index of the first element in `items` that is greater than or equal to `context`,
- upperBound
- Returns the index of the first element in `items` that is greater than `context`, as determined
- partitionPoint
- Returns the index of the partition point of `items` in relation to the given predicate.
- equalRange
- Returns a tuple of the lower and upper indices in `items` between which all
Source
Implementation
pub fn heapContext(a: usize, b: usize, context: anytype) void {
assert(a <= b);
// build the heap in linear time.
var i = a + (b - a) / 2;
while (i > a) {
i -= 1;
siftDown(a, i, b, context);
}
// pop maximal elements from the heap.
i = b;
while (i > a) {
i -= 1;
context.swap(a, i);
siftDown(a, a, i, context);
}
}