src/core/siftdown.js
import nextchild from './nextchild.js';
/**
* Sifts down a node.
*
* @param {int} arity arity of the heap
* @param {function} compare the comparison function
* @param {function} swap the swap function
* @param {array} a the array where the heap is stored
* @param {int} i is the root element
* @param {int} j - 1 is the last leaf
* @param {int} k is the target node
*/
export default function siftdown(arity, compare, swap, a, i, j, k) {
let current = k - i;
while (true) {
// Address of the first child in a zero-based
// d-ary heap
const firstchild = arity * current + 1;
// If current node has no children
// then we are done
if (firstchild >= j - i) break;
// If current value is smaller than its smallest
// child then we are done
const candidate = nextchild(arity, compare, swap, a, i + firstchild, j);
if (compare(a[i + current], a[candidate]) <= 0) break;
// Otherwise
// swap with smallest child
swap(a, i + current, candidate);
current = candidate - i;
}
return i + current;
}