heap.js

/*

Heap Property:

* MinHeap: For every object x, the key of x is <= the keys of its children
* MaxHeap: For every object x, the key of x is >= the keys of its children

----------------------------------------------------------------------------------------------------

Insert:

1. Add object x onto the end of the array and increment the array size
2. Repeatedly swap the object x and the parent of x while there is a heap violation

----------------------------------------------------------------------------------------------------

Extract(Min/Max):

1. Store the value of the first item at index 0 to be returned
2. Set the value of the first item at index 0 to the last item of the array and decrement the array size
3. Repeatedly swap the object x and the min/max child of x while there is a heap violation
4. Return the value of the first item stored in step 1

*/

let key = x => Array.isArray(x) ? x[0] : x;
let heappush = (A, x, f = Math.min) => {
    let P = i => Math.floor((i - 1) / 2);  // parent
    A.push(x);
    let N = A.length,
        i = N - 1;
    while (0 < i && key(A[i]) == f(key(A[i]), key(A[P(i)]))) {
        [A[i], A[P(i)]] = [A[P(i)], A[i]];
        i = P(i);
    }
};
let heappop = (A, f = Math.min) => {
    let L = i => 2 * i + 1,  // children
        R = i => 2 * i + 2;
    let N = A.length,
        i = 0;
    let top = A[0];
    [A[0], A[N - 1]] = [A[N - 1], A[0]], A.pop(), --N;
    let ok;
    do {
        ok = true;
        let left = f == Math.min ? Infinity : -Infinity,
            right = left;
        if (L(i) < N && key(A[i]) != f(key(A[i]), key(A[L(i)]))) ok = false, left  = key(A[L(i)]);
        if (R(i) < N && key(A[i]) != f(key(A[i]), key(A[R(i)]))) ok = false, right = key(A[R(i)]);
        if (!ok) {
            let j = left == f(left, right) ? L(i) : R(i);
            [A[i], A[j]] = [A[j], A[i]];
            i = j;
        }
    } while (!ok);
    return top;
};