Skip to content

Instantly share code, notes, and snippets.

@prettymuchbryce
Created September 23, 2012 02:08
Show Gist options
  • Save prettymuchbryce/3768553 to your computer and use it in GitHub Desktop.
Save prettymuchbryce/3768553 to your computer and use it in GitHub Desktop.
Javascript Priority Queue Implementation
//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;
}
}
@ldedier
Copy link

ldedier commented Oct 13, 2019

hello, have to put this.length in lines:
38 39 57 62

:)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment