# Javascript PriorityQueue based on object property

Posted on

Problem

I wrote this class which is a priority queue based on a numeric property of any object. As far as I can tell, the following code is working as intended. Are there any stylistic tendencies that I am getting wrong, or any gotchas I should look out for?

``````//Constants

PriorityQueue.MAX_HEAP = 0;
PriorityQueue.MIN_HEAP = 1;

/**
* This is an improved Priority Queue data type implementation that can be used to sort any object type.
* It uses a technique called a binary heap.
*
* For more on binary heaps see: http://en.wikipedia.org/wiki/Binary_heap
*
* @param criteria The criteria by which to sort the objects. This should be a property of the objects you're sorting.
* @param heapType either PriorityQueue.MAX_HEAP or PriorityQueue.MIN_HEAP.
**/
function PriorityQueue(criteria,heapType) {
this.length = 0; //The current length of heap.
var queue = [];
var isMax = false;

//Constructor
if (heapType==PriorityQueue.MAX_HEAP) {
isMax = true;
} else if (heapType==PriorityQueue.MIN_HEAP) {
isMax = false;
} else {
throw heapType + " not supported.";
}

/**
* Inserts the value into the heap and sorts it.
*
* @param value The object to insert into the heap.
**/
this.insert = function(value) {
if (!value.hasOwnProperty(criteria)) {
throw "Cannot insert " + value + " because it does not have a property by the name of " + criteria + ".";
}
queue.push(value);
length++;
bubbleUp(length-1);
}

/**
* Peeks at the highest priority element.
*
* @return the highest priority element
**/
this.getHighestPriorityElement = function() {
return queue[0];
}

/**
* Removes and returns the highest priority element from the queue.
*
* @return the highest priority element
**/
this.shiftHighestPriorityElement = function() {
if (length < 0) {
throw ("There are no more elements in your priority queue.");
}
var oldRoot = queue[0];
var newRoot = _queue.pop();
length--;
queue[0] = newRoot;
swapUntilQueueIsCorrect(0);
return oldRoot;
}

var bubbleUp = function(index) {
if (index==0) {
return;
}
var parent = getParentOf(index);
if (evaluate(index,parent)) {
swap(index,parent);
bubbleUp(parent);
} else {
return;
}
}

var swapUntilQueueIsCorrect = function(value) {
left = getLeftOf(value);
right = getRightOf(value);
if (evaluate(left,value)) {
swap(value,left);
swapUntilQueueIsCorrect(left);
} else if (evaluate(right,value)) {
swap(value,right);
swapUntilQueueIsCorrect(right);
} else if (value==0) {
return;
} else {
swapUntilQueueIsCorrect(0);
}
}

var swap = function(self,target) {
var placeHolder = queue[self];
queue[self] = queue[target];
queue[target] = placeHolder;
}

/*
/*Helpers
*/
var evaluate = function(self,target) {
if (queue[target]==null||queue[self]==null) {
return false;
}
if (isMax) {
if (queue[self][criteria] > queue[target][criteria]) {
return true;
} else {
return false;
}
} else {
if (queue[self][criteria] < queue[target][criteria]) {
return true;
} else {
return false;
}
}
}

var getParentOf = function(index) {
return Math.floor(index/2)-1;
}

var getLeftOf = function(index) {
return index*2 + 1;
}

var getRightOf = function(index) {
return index*2 + 2;
}
}
``````

Solution

You’re off to a great start. +1 for providing comments.

Here are some tips:

## 1) Define variables before modifying them.

So the constants `MAX_HEAP` and `MIN_HEAP` should be defined after `PriorityQueue`.

Old Code:

``````PriorityQueue.MAX_HEAP = 0;
PriorityQueue.MIN_HEAP = 1;

function PriorityQueue(criteria, heapType) {
//...
}
``````

New Code:

``````function PriorityQueue(criteria, heapType) {
//...
}
PriorityQueue.MAX_HEAP = 0;
PriorityQueue.MIN_HEAP = 1;
``````

Side note: In `shiftHighestPriorityElement()`, `_queue` isn’t defined. I think it should be `queue`.

## 2) Use `this` to attach attributes to a Constructor.

Example:
Old Code:

``````//..
function PriorityQueue(criteria, heapType) {
this.length = 0;
var queue = [];
var isMax = false;
//...
``````

New Code:

``````//..
function PriorityQueue(criteria, heapType) {
this.length = 0;
this.queue = [];
this.isMax = false;
//...
``````

## 3) Split up functions longer than 8 – 12 lines of code into smaller functions.

Use the prototype on an object to attach functions to the constructor instead of including all the functionality within.

Old Code:

``````function PriorityQueue(criteria, heapType) {
//...
this.insert = function (value) {
if (!value.hasOwnProperty(criteria)) {
throw "Cannot insert " + value + " because it does not have a property by the name of " + criteria + ".";
}
queue.push(value);
length++;
bubbleUp(length - 1);
}
//...
var swap = function (self, target) {
var placeHolder = queue[self];
queue[self] = queue[target];
queue[target] = placeHolder;
}
//...
}
``````

New Code:

``````function PriorityQueue(criteria, heapType) {
//...
}
PriorityQueue.prototype.insert = function (value) {
if (!value.hasOwnProperty(this.criteria)) {
throw "Cannot insert " + value + " because it does not have a property by the name of " + this.criteria + ".";
}
this.queue.push(value);
this.length++;
this.bubbleUp(this.length - 1);
}
PriorityQueue.prototype.swap = function (self, target) {
var placeHolder = this.queue[self];
this.queue[self] = this.queue[target];
this.queue[target] = placeHolder;
}
``````

## 4) Sometimes it’s better to just return an boolean expression.

Old Code:

``````if (queue[self][criteria] < queue[target][criteria]) {
return true;
} else {
return false;
}
``````

New Code:

``````return (queue[self][criteria] < queue[target][criteria]);
``````

Try out qunit.js

## 6) Simplify `if` and `else` conditions.

Old Code:

``````var isMax = false;

//Constructor
if (heapType==PriorityQueue.MAX_HEAP) {
isMax = true;
} else if (heapType==PriorityQueue.MIN_HEAP) {
isMax = false;
} else {
throw heapType + " not supported.";
}
``````

New Code:

``````this.isMax = !!heapType;
if ( heapType !== 0 || heapType !== 1 ){
throw heapType + " not supported.";
}
``````

## 7) Use `===` instead of `==` when comparing for value and type of primitive values.

Old code:

``````} else if (value == 0) {
``````

New Code:

``````} else if (value === 0) {
``````

Or

``````} else if (!value) {
``````

## Final code:

``````function PriorityQueue(criteria, heapType) {
this.criteria = criteria;
this.length = 0;
this.queue = [];
this.isMax = !!heapType;
if ( heapType !== 0 || heapType !== 1 ){
throw heapType + " not supported.";
}
}
PriorityQueue.prototype.insert = function (value) {
if (!value.hasOwnProperty(this.criteria)) {
throw "Cannot insert " + value + " because it does not have a property by the name of " + this.criteria + ".";
}
this.queue.push(value);
this.length++;
this.bubbleUp(this.length - 1);
};
PriorityQueue.prototype.getHighestPriorityElement = function () {
return this.queue[0];
};
PriorityQueue.prototype.shiftHighestPriorityElement = function () {
if (length < 0) {
throw("There are no more elements in your priority queue.");
}
var oldRoot = this.queue[0];
var newRoot = this.queue.pop();
this.length--;
this.queue[0] = newRoot;
this.swapUntilQueueIsCorrect(0);
return oldRoot;
};
PriorityQueue.prototype.bubbleUp = function (index) {
if (index === 0) {
return;
}
var parent = this.getParentOf(index);
if (this.evaluate(index, parent)) {
this.swap(index, parent);
this.bubbleUp(parent);
} else {
return;
}
};
PriorityQueue.prototype.swapUntilQueueIsCorrect = function (value) {
var left = this.getLeftOf(value),
right = this.getRightOf(value);

if (this.evaluate(left, value)) {
this.swap(value, left);
this.swapUntilQueueIsCorrect(left);
} else if (this.evaluate(right, value)) {
this.swap(value, right);
this.swapUntilQueueIsCorrect(right);
} else if (value === 0) {
return;
} else {
this.swapUntilQueueIsCorrect(0);
}
};
PriorityQueue.prototype.swap = function (self, target) {
var placeHolder = this.queue[self];
this.queue[self] = this.queue[target];
this.queue[target] = placeHolder;
};
PriorityQueue.prototype.evaluate = function (self, target) {
if (this.queue[target] === null || this.queue[self] === null) {
return false;
}
if (this.isMax) {
return (this.queue[self][this.criteria] > this.queue[target][this.criteria]);
} else {
return (this.queue[self][this.criteria] < this.queue[target][this.criteria]);
}
};
PriorityQueue.prototype.getParentOf = function (index) {
return Math.floor(index / 2) - 1;
};
PriorityQueue.prototype.getLeftOf = function (index) {
return index * 2 + 1;
};
PriorityQueue.prototype.getRightOf = function (index) {
return index * 2 + 2;
};
PriorityQueue.MAX_HEAP = 0;
PriorityQueue.MIN_HEAP = 1;
``````