minheap

minheap.js

/*jslint beta, devel*/

function minheapHeapify(arr, compareFn) {
/**
 * Converts an array into a min-heap.
 *
 * @param {Array} arr The array to be converted into a min-heap.
 * @param {function} compareFn The comparator function (a, b) => a - b
 * for min-heap.
 */
    let ii;
    let jj = Math.floor(arr.length / 2);
    let left;
    let length = arr.length;
    let right;
    let smallest;
    while (jj >= 0) {
        ii = jj;
        // sift-down
        while (ii < length) {
            left = 2 * ii + 1;
            right = 2 * ii + 2;
            smallest = ii;
            if (left < length && compareFn(arr[left], arr[smallest]) < 0) {
                smallest = left;
            }
            if (right < length && compareFn(arr[right], arr[smallest]) < 0) {
                smallest = right;
            }
            if (smallest !== ii) {
                [arr[ii], arr[smallest]] = [arr[smallest], arr[ii]];
                ii = smallest;
            } else {
                break;
            }
        }
        jj -= 1;
    }
}

function minheapPop(arr, compareFn) {
/**
 * Removes and returns the minimum element from a min-heap.
 *
 * @param {Array} arr The heap array.
 * @param {function} compareFn The comparator function (a, b) => a - b
 *     for min-heap.
 * @returns {*} The minimum element, or undefined if the heap is empty.
 */
    let ii = 0;
    let left;
    let length = arr.length - 1;
    let peek;
    let right;
    let smallest;
    if (length <= 0) {
        return arr.pop();
    }
    peek = arr[0];
    arr[0] = arr.pop();
    // sift-down
    while (ii < length) {
        left = 2 * ii + 1;
        right = 2 * ii + 2;
        smallest = ii;
        if (left < length && compareFn(arr[left], arr[smallest]) < 0) {
            smallest = left;
        }
        if (right < length && compareFn(arr[right], arr[smallest]) < 0) {
            smallest = right;
        }
        if (smallest !== ii) {
            [arr[ii], arr[smallest]] = [arr[smallest], arr[ii]];
            ii = smallest;
        } else {
            break;
        }
    }
    return peek;
}

function minheapPush(arr, compareFn, elem) {
/**
 * Inserts an element into a min-heap.
 *
 * @param {Array} arr The heap array.
 * @param {function} compareFn The comparator function (a, b) => a - b
 *     for min-heap.
 * @param {*} elem The element to insert.
 */
    let ii = arr.length;
    let parent;
    arr.push(elem);
    // sift-up
    while (ii > 0) {
        parent = Math.floor((ii - 1) / 2);
        if (compareFn(arr[ii], arr[parent]) < 0) {
            [arr[ii], arr[parent]] = [arr[parent], arr[ii]];
            ii = parent;
        } else {
            break;
        }
    }
}

(function () {
    let arr = [];
    let ii = 0;
    function compareFn(aa, bb) {
        return aa[1] - bb[1];
    }
    while (ii < 8) {
        //!! minheapPush(arr, compareFn, [ii, Math.random()]);
        arr.push([ii, Math.random()]);
        ii += 1;
    }
    minheapHeapify(arr, compareFn);
    while (arr.length) {
        console.log(minheapPop(arr, compareFn));
    }
}());