Skip to content

Instantly share code, notes, and snippets.

@fabianuribe fabianuribe/heap.js
Last active Apr 10, 2016

Embed
What would you like to do?
The Heap Data Structure in Javascript
/**
* 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;
}
};
// 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);
});
});
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.