Heap - ES2015

by Hari Menon

JavaScript

'use strict';
// Heap Base Class
class Heap {
    constructor(array, heapType) {
        this.items = [];
        this.heapSize = 0;
        if (!heapType) {
            // should be set to 'MIN' or 'MAX' from the sub classes
            throw new Error('heapType should be \'MIN\' or \'MAX\'');
        }
        this.type = heapType;
        if (array instanceof Array && array.length) {
            this.buildHeap(array);
        } else if (array instanceof Object && array.key) {
            this.buildHeap([array]);
        }
    }

    static parent(index) {
        return Math.floor(index - 1 / 2);
    }

    static left(index) {
        return 2 * index + 1;
    }

    static right(index) {
        return 2 * index + 2;
    }

    ensureHeapProperty(node, invariant) {
        // console.log('Checking %d and %d', node, invariant);
        if (this.type === 'MIN') {
            return node < invariant;
        }
        return node > invariant;
    }

    buildHeap(array) {
        this.items = array;
        this.heapSize = array.length;
        for (var i = Math.floor((array.length - 1) / 2); i >= 0; i--) {
            // console.log('Calling this.heapify(%d)', i);
            this.heapify(i);
        }
    }

    heapify(index) {
        // console.log('Heapify(%d)', index);
        var left = Heap.left(index);
        var right = Heap.right(index);
        var invariant = index;
        // console.log('Left: %d, Right: %d, Invariant: %d, items[index]: %d, items[left]: %d, items[right]: %d', left, right, invariant, this.items[index], this.items[left], this.items[right]);

        if ((left < this.heapSize) && this.ensureHeapProperty(this.items[left], this.items[invariant])) {
            invariant = left;
        }

        if ((right < this.heapSize) && this.ensureHeapProperty(this.items[right], this.items[invariant])) {
            invariant = right;
        }

        if (invariant !== index) {
            // console.log('Swapping %d (%d) and %d (%d)',...