The Heap Data Structure in Javascript

heap.js

/**
 * heap.js
 * A module that implements a Doubly Linked List data Structure
 * @module LinkedList
 */
module.exports = Heap;
var TYPE_MIN = 'min';
var TYPE_MAX = 'max';

/**
 * Represents a Heap.
 * @constructor
 */
function Heap (array, type, compareFunction) {
    this.array = array || [];
    this.type = type === TYPE_MIN ? TYPE_MIN : TYPE_MAX;
    this.compare = (typeof compareFunction === 'function') ? compareFunction : this.defaultCompareFunction;
    this.buildHeap();
}

Heap.prototype = {
    /**
     * Arranges the array as a valid heap,
     * On a 'Max' Heap all the childs should be smaller than their parents
     * On a 'Min' Heap all the childs should be greater than their parents
     */
    buildHeap: function () {
        var last = this.array.length - 1;
        var middle = Math.floor(last/2);
        var i;
        for (i = middle; i >= 0; i -= 1) {
            this._heapify(i);
        }
    },

    /**
     * Sorts the array 'in place' according to the Heap type,
     * A 'Max' Heap will be sorted in ascending order.
     * A 'Min' Heap will be sorted in descending order.
     */
    sort: function () {
        var limit = this._getLastIdx();
        while (limit > 0) {
            this._swap(0, limit);
            limit -= 1;
            if (limit) {
                this._heapify(0, limit);
            }
        }
    },

    /**
     * Adds an element to the Heap maintaing its order.
     * @param {Object} element
     */
    insert: function (element) {
        this.array.push(element);
        this._bubbleUp(this._getLastIdx());
    },

    /**
     * Removes the first elment of the Heap
     * @return {Object}
     */
    removeTop: function () {
        var top = this.array[0];
        this._swap(0, this._getLastIdx());
        this.array.pop();
        this._heapify(0);
        return top;
    },

    /**
     * Compares two objects with Javascript's native logic.
     * @param {Object} a
     * @param {Object} b
     * @return {Number}
     */
    defaultCompareFunction: function (a, b) {
        if (a > b) {
            return 1;
        }
        if (b > a) {
            return -1;
        }
        return 0;
    },

    /**
     * Makes a valid Heap top down
     * @private
     * @param {Number} startIdx
     * @param {Number} limitIdx
     */
    _heapify: function (startIdx, limitIdx) {
        limitIdx = limitIdx || this._getLastIdx();
        var topIdx = startIdx;
        var top = this.array[topIdx];
        var leftIdx = this._getLeftChild(startIdx, limitIdx);
        var rightIdx = this._getRightChild(startIdx, limitIdx);
        var left = leftIdx && this.array[leftIdx];
        var right = rightIdx && this.array[rightIdx];

        if (startIdx > limitIdx) {
            return;
        }

        if (left &&
            ((this.type === TYPE_MIN && this.compare(left, top) < 0) ||
            (this.type === TYPE_MAX && this.compare(left, top) > 0))) {
            topIdx = leftIdx;
            top = left;
        }

        if (right &&
            ((this.type === TYPE_MIN && this.compare(right, top) < 0) ||
            (this.type === TYPE_MAX && this.compare(right, top) > 0))) {
            topIdx = rightIdx;
            top = right;
        }

        if (startIdx !== topIdx) {
            this._swap(startIdx, topIdx);
            this._heapify(topIdx, limitIdx);
        }
    },

    /**
     * Interchanges the elements at two indexes
     * @private
     * @param {Object} a
     * @param {Object} b
     */
    _swap: function (a, b) {
        var temp = this.array[a];
        this.array[a] = this.array[b];
        this.array[b] = temp;
    },

    /**
     * Maintains the heap property by comparing an elment to it's parent,
     * swaping it if necessary until finding the correct position where 
     * the Heap is valid.
     * @private
     * @param {Number} index - The elment to bubble up.
     */
    _bubbleUp: function(index) {
        var parentIdx = this._getParent(index);
        var parent = (parentIdx >= 0) ? this.array[parentIdx] : null;
        var value = this.array[index];

        if (parent === null) {
            return;
        }
        if ((this.type === TYPE_MIN && this.compare(value, parent) < 0) ||
            (this.type === TYPE_MAX && this.compare(value, parent) > 0)) {
            this._swap(index, parentIdx);
            this._bubbleUp(parentIdx);
        }
    },

    /**
     * Returns the left child index of a parent.
     * @access private
     * @param {Numer} parent - The parent's index.
     * @param {Number} limit - Bound until a child's index will be returned.
     * @return {Number|null}
     */
    _getLeftChild: function (parent, limit) {
        limit = limit || this._getLastIdx();
        var childIndex = parent * 2 + 1;
        return (childIndex <= limit) ? childIndex : null;
    },

    /**
     * Returns the right child index of a parent.
     * @access private
     * @param {Numer} parent - The parent's index.
     * @param {Number} limit - Bound until a child's index will be returned.
     * @return {Number|null}
     */
    _getRightChild: function (parent, limit) {
        limit = limit || this._getLastIdx();
        var childIndex = parent * 2 + 2;
        return (childIndex <= limit) ? childIndex : null;
    },

    /**
     * Returns the parent index of a child.
     * @access private
     * @param {Number} index
     * @return {Number}
     */
    _getParent: function (index) {
        if (index % 2) {
            // Is left child
            return (index - 1)/2;
        }
        // Is right child
        return (index/2) - 1;
    },

    /**
     * Returns the index of the last element of the Heap.
     * @access private
     * @return {Number}
     */
    _getLastIdx: function () {
        var size = this.array.length;
        return size > 1 ? size - 1 : 0;
    }
};

heap_test.js

// Libraries
var assert = require('chai').assert;
var expect = require('chai').expect;
var Heap = require('heap.js');

// Helpers
var helpers = {
    isValidHeap: function (heap) {
        var leftIdx;
        var rightIdx;
        var left;
        var right;
        var i;

        for (i = 0; i < heap.array.length ; i += 1) {
            element = heap.array[i];
            leftIdx = i * 2 + 1;
            rightIdx = i * 2 + 2;
            left = heap.array[leftIdx];
            right = heap.array[rightIdx];
            if (left &&
                ((heap.type === 'max' && heap.compare(element, left) < 0) ||
                (heap.type === 'min' && heap.compare(element, left) > 0))) {
                return false;
            }
            if (right &&
                ((heap.type === 'max' && heap.compare(element, right) < 0) ||
                (heap.type === 'min' && heap.compare(element, right) > 0))) {
                return false;
            }
        }
        return true;
    },

    isSameArray: function  (a, b) {
        var i;
        if (!a || !b) {
            console.log('Invalid input');
            return false;
        }
        if (a.length !== b.length) {
            console.log('Different sizes');
            return false;
        }
        for (i = 0; i < a.length; i += 1) {
            if (a[i] !== b[i]) {
                console.log(a[i], 'is different than ', b[i]);
                return false;
            }
        }
        return true;
    },

    familyCompareFunction: function (a, b) {
        if (a.children > b.children) {
            return 1;
        }
        if (b.children > a.children) {
            return -1;
        }
        return 0;
    }
};


// Mock data
var ascendingArray = [1,2,3,4,5,6,7,8];
var descendingArray = [8,7,6,5,4,3,2,1];
var randomArray = [4,6,1,0,3,7,8,5,8];
var sortedRandomArray = [0,1,3,4,5,6,7,8,8];
var familyA = { children: 0, parents: 2 };
var familyB = { children: 2, parents: 1 };
var familyC = { children: 4, parents: 2 };
var familyD = { children: 6, parents: 2 };
var sortedFamiliesArray = [familyA, familyB, familyC, familyD];
var unsortedFamiliesArray = [familyB, familyA, familyD, familyC];
var descHeap;
var ascHeap;
var randHeap;
var familyHeap;

beforeEach(function() {
    descHeap = new Heap(descendingArray, 'min');
    ascHeap = new Heap(ascendingArray, 'max');
    randHeap = new Heap(randomArray);
    familyHeap = new Heap(unsortedFamiliesArray, 'max', helpers.familyCompareFunction);
});

describe('Heap', function () {
    describe('buildHeap', function () {
        it('Should build a Min Heap', function () {
            assert.equal(helpers.isValidHeap(descHeap), true);
            expect(descHeap.array[0]).to.be.below(descHeap.array[1]);
        });

        it('Should build Max a Heap', function () {
            assert.equal(helpers.isValidHeap(ascHeap), true);
            expect(ascHeap.array[0]).to.be.above(ascHeap.array[1]);
        });

        it('Should build a Max Heap when no type is specified', function () {
            assert.equal(helpers.isValidHeap(randHeap), true);
            expect(randHeap.array[0]).to.be.above(randHeap.array[1]);
        });

        it('Should build a valid Heap of custom objects', function () {
            assert.equal(helpers.isValidHeap(familyHeap), true);
        });
    });

    describe('insert', function () {
        it('Should insert an element to the heap', function () {
            ascHeap.insert(10);
            assert.equal(ascHeap.array[0], 10);
            ascHeap.insert(11);
            assert.equal(ascHeap.array[0], 11);
        });

        it ('Should maintain a valid heap after insertion', function () {
            ascHeap.insert(10); // Upper Limit
            assert.equal(helpers.isValidHeap(ascHeap), true);
            ascHeap.insert(0); // Lower Limit
            assert.equal(helpers.isValidHeap(ascHeap), true);
            ascHeap.insert(5); // Middle (duplicate)
            assert.equal(helpers.isValidHeap(ascHeap), true);
        });
    });

    describe('sort', function () {
        it('Should return an ascending array when is a max Heap', function () {
            ascHeap.sort();
            assert.equal(helpers.isSameArray(ascHeap.array, ascendingArray), true);
        });

        it('Should return a descending Array when is a min Heap', function () {
            descHeap.sort();
            assert.equal(helpers.isSameArray(descHeap.array, descendingArray), true);
        });

        it('Should sort duplicate items correctly', function () {
            randHeap.sort();
            assert.equal(helpers.isSameArray(randHeap.array, sortedRandomArray), true);
        });

        it('Should sort correctly when using a custom comparing function', function () {
            familyHeap.sort();
            assert.equal(familyHeap.array[0], sortedFamiliesArray[0]);
            assert.equal(familyHeap.array[1], sortedFamiliesArray[1]);
            assert.equal(familyHeap.array[2], sortedFamiliesArray[2]);
            assert.equal(familyHeap.array[3], sortedFamiliesArray[3]);
        });
    });

    describe('removeTop', function () {
        it('Should return the first element', function () {
            var top = descHeap.removeTop();
            assert.equal(top, 1);
        });

        it ('Should decrease heap size', function () {
            var initialSize = descHeap.array.length;
            descHeap.removeTop();
            assert.equal(descHeap.array.length, initialSize - 1);
        });

        it ('Should leave a valid Heap', function () {
            descHeap.removeTop();
            assert.equal(helpers.isValidHeap(descHeap), true);
        });
    });
});