5
\$\begingroup\$

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;
    }
}
\$\endgroup\$
8
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ Wow! These are some great tips. Thanks much Larry. \$\endgroup\$ – prettymuchbryce Oct 2 '12 at 4:03
  • 1
    \$\begingroup\$ For anyone who, like me, wants to use this code for their own purposes, there is a small error. The getParentOf function uses a Math.floor . All odd indices will evaluate to having a wrong parent (e.g. index 1 will evaluate to parent -1). This can be fixed by changing Math.floor to Math.ceil \$\endgroup\$ – Poelie Sep 28 '16 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.