Data Structures in Javascript: Heaps
31 October 2015
The Heap is a great example of how the right data structure can dramatically change the performance of an algorithm, sorting using Heapsort can be achieved in linearithmic time and constant space.

A Heap is a tree-based data structure, it is very efficient executing operations of a priority queue, such as inserts and getting the min/max. A Heap can be classified as a Max Heap or a Min Heap . In order to satisfy the Heap property, in a Max Heap the value on all the parent nodes should be greater than or equal to its children value. On the other hand in a Min Heap the value on all the parent nodes will be less than or equal to its children value.

The implementation
A simple Array allows us to store a Heap without the need of pointers. Where the index for the children of each parent can be obtained:

Left = Parent * 2 + 1
Right = Parent * 2 + 2

The Heap will implement the following basic operations :

Build
Insert
Remove Top
Search
String representation
/**
* 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;
}
};
The complete source code for this data structure’s including the unit tests for this implementation are included here .

Complexity
Operation
Complexity
Sort
O(n log n)
Search
O(n)
Insert
O(log n)
Delete
O(log n)
Max/Min
O(1)

The Good
Sorting is achieved in best time space/complexity.
The Bad
Searching is slow since we can’t leverage fast searching algorithms such as Binary Search.