Javascript PriorityQueue based on object property

By 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.

More info

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]);

5) Make sure to create test units.

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;

Leave a Reply

Your email address will not be published. Required fields are marked *