DoxigAlpha
std › sort.siftDown

siftDown

Function parameters

Parameters

#
a:usize
target: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

#
fn siftDown(a: usize, target: usize, b: usize, context: anytype) void {
    var cur = target;
    while (true) {
        // When we don't overflow from the multiply below, the following expression equals (2*cur) - (2*a) + a + 1
        // The `+ a + 1` is safe because:
        //  for `a > 0` then `2a >= a + 1`.
        //  for `a = 0`, the expression equals `2*cur+1`. `2*cur` is an even number, therefore adding 1 is safe.
        var child = (math.mul(usize, cur - a, 2) catch break) + a + 1;

        // stop if we overshot the boundary
        if (!(child < b)) break;

        // `next_child` is at most `b`, therefore no overflow is possible
        const next_child = child + 1;

        // store the greater child in `child`
        if (next_child < b and context.lessThan(child, next_child)) {
            child = next_child;
        }

        // stop if the Heap invariant holds at `cur`.
        if (context.lessThan(child, cur)) break;

        // swap `cur` with the greater child,
        // move one step down, and continue sifting.
        context.swap(child, cur);
        cur = child;
    }
}