heap
Unstable in-place sort. O(n*log(n)) best case, worst case and average case.
O(1) memory (no allocator required).
Sorts in ascending order with respect to the given lessThan function.
Function parameters
Parameters
- T:type
- items:[]T
- context:anytype
- lessThanFn:fn (@TypeOf(context), lhs: T, rhs: T) bool
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 heap(
comptime T: type,
items: []T,
context: anytype,
comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) void {
const Context = struct {
items: []T,
sub_ctx: @TypeOf(context),
pub fn lessThan(ctx: @This(), a: usize, b: usize) bool {
return lessThanFn(ctx.sub_ctx, ctx.items[a], ctx.items[b]);
}
pub fn swap(ctx: @This(), a: usize, b: usize) void {
return mem.swap(T, &ctx.items[a], &ctx.items[b]);
}
};
heapContext(0, items.len, Context{ .items = items, .sub_ctx = context });
}