javascript binary-min-heap

heap.js

/* jslint utility2:true */
(function () {
/*
 * this function will provide a binary-min-heap in javascript
 */
    "use strict";
    let heapCreate;
    let heapDecreaseKey;
    let heapDelete;
    let heapHeapify;
    let heapInsert;
    let heapPeek;
    let heapPop;
    let heapSiftUp;
    let heapSwap;
    heapCreate = function (list = []) {
    /*
     * this function will create min-heap from <list>
     */
        let heap;
        let ii;
        heap = [];
        ii = 0;
        while (ii < list.length) {
            heapInsert(heap, list[ii]);
            ii += 1;
        }
        return heap;
    };
    heapDecreaseKey = function (list, ii, key) {
    /*
     * this function will decrease <list>[<ii>][0] to <key>
     * and assume <key> is smaller than <list>[<ii>][0].
     */
        list[ii][0] = key;
        heapSiftUp(list, ii);
    };
    heapDelete = function (list, ii) {
    /*
     * this function will delete elem <list>[<ii>] by sifting and popping it
     */
        list[ii][0] = list[0][0] - 1;
        heapSiftUp(list, ii);
        return heapPop(list);
    };
    heapHeapify = function (list, ii) {
    /*
     * this function will recursively heapify subtree <list>[<ii>]
     * and assume subtrees are already heapified
     */
        let ll;
        let rr;
        let smallest;
        ll = 2 * ii + 1;
        rr = 2 * ii + 2;
        smallest = ii;
        if (ll < list.length && list[ll][0] < list[ii][0]) {
            smallest = ll;
        }
        if (rr < list.length && list[rr][0] < list[smallest][0]) {
            smallest = rr;
        }
        if (smallest !== ii) {
            heapSwap(list, ii, smallest);
            // recurse
            heapHeapify(list, smallest);
        }
    };
    heapInsert = function (list, elem) {
    /*
     * this function will append <elem> to <list> and sift it up
     * until min-heap-property is restored
     */
        list.push(elem);
        heapSiftUp(list, list.length - 1);
    };
    heapPeek = function (list) {
    /*
     * this function will peek min-elem from <list> without popping
     */
        return list[0];
    };
    heapPop = function (list) {
    /*
     * this function will pop min-elem from <list>
     */
        let root;
        if (list.length <= 1) {
            return list.shift();
        }
        // pop min-elem and re-heapify
        root = list.shift();
        heapHeapify(list, 0);
        return root;
    };
    heapSiftUp = function (list, ii) {
    /*
     * this function will move elem <list>[<ii>] up <list>
     * until min-heap-property is restored
     */
        let jj;
        while (ii !== 0) {
            jj = (ii - 1) >>> 1;
            if (list[jj][0] < list[ii][0]) {
                return;
            }
            heapSwap(list, ii, jj);
            ii = jj;
        }
    };
    heapSwap = function (list, ii, jj) {
    /*
     * this function will swap elem <list>[<ii>] with elem <list>[<jj>]
     */
        let tmp;
        tmp = list[ii];
        list[ii] = list[jj];
        list[jj] = tmp;
    };
    // Driver program to test above functions
    let hh;
    hh = heapCreate();
    heapInsert(hh, [
        3
    ]);
    heapInsert(hh, [
        2
    ]);
    heapDelete(hh, 1);
    heapInsert(hh, [
        15
    ]);
    heapInsert(hh, [
        5
    ]);
    heapInsert(hh, [
        4
    ]);
    heapInsert(hh, [
        45
    ]);
    console.log(hh);
    console.log(heapPop(hh));
    console.log(heapPeek(hh));
    heapDecreaseKey(hh, 2, 1);
    console.log(heapPeek(hh));
}());