Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Priority Queue - Jamis Buck - Challenge #5
<!DOCTYPE html>
<html>
<head>
<title>Priority Queue with binary heap</title>
<meta charset="utf-8" />
<link rel="stylesheet" href="https://code.jquery.com/qunit/qunit-2.0.1.css">
</head>
<body>
<div id="qunit"></div>
<div id="qunit-fixture"></div>
<script src="https://code.jquery.com/qunit/qunit-2.0.1.js"></script>
<script type="text/javascript">
var binary_heap = function (type, capacity) {
if (!type || (type !== "min" && type !== "max"))
type = "min";
if (!capacity)
capacity = 10;
this.type = type;
this.heap = new Array(capacity);
this.current_size = 0;
};
binary_heap.prototype.is_empty = function() {
return this.current_size === 0;
}
binary_heap.prototype.is_full = function() {
return this.current_size + 1 === this.heap.length;
}
binary_heap.prototype.enlarge_array = function() {
this.heap.length += this.heap.length;
}
binary_heap.prototype.order_is_valid = function(a, b) {
if (this.type === "min")
return a.priority < b.priority;
else
return a.priority > b.priority;
}
binary_heap.prototype.insert = function(element) {
if (this.is_full())
this.enlarge_array();
this.heap[this.current_size + 1] = element;
// percolate up
var hole = ++this.current_size;
while(hole > 1 && this.order_is_valid(element, this.heap[parseInt(hole / 2)])) {
this.heap[hole] = this.heap[parseInt(hole / 2)];
hole = parseInt(hole / 2);
}
this.heap[hole] = element;
};
binary_heap.prototype.extract = function() {
if (this.is_empty())
throw "Queue is empty"
var minNode = this.heap[1];
this.percolate_down(1);
return minNode;
}
/* A hole is created inside the queue and it is temporaly filled
* with the last element of the queue. We start percolating down the hole
* until a valid position can be found for last element i.e. a position in which
* both children have a smaller value than their parent.
*
* Steps:
* 1. Compare both children to detect wich one is the smallest
* 2. Compare smallest child with tmp
* - If child is smaller then we move it up the tree. The hole is now located at
* the previous location of the child (percolate down)
* - If child is greater then we put the tmp value inside the hole
* and we are done
*/
binary_heap.prototype.percolate_down = function(hole) {
var tmp = this.heap[this.current_size];
var child = 0;
this.heap[hole] = tmp;
for ( ; hole * 2 <= this.current_size; hole = child) {
child = hole * 2;
if (child < this.current_size && this.order_is_valid(this.heap[child + 1], this.heap[child]))
child++;
if (this.order_is_valid(this.heap[child], tmp)){
this.heap[hole] = this.heap[child];
} else {
break;
}
}
this.heap[hole] = tmp;
this.heap[this.current_size] = undefined;
--this.current_size;
}
var priority_queue = function (type) {
this.bh = new binary_heap(type);
};
priority_queue.prototype.enqueue = function(element) {
this.bh.insert(element);
}
priority_queue.prototype.dequeue = function(element) {
return this.bh.extract();
}
</script>
<script type="text/javascript">
QUnit.test("Initialization - no type", function (assert) {
var pq = new priority_queue();
assert.ok(pq.bh.type === "min", "Passed!");
});
QUnit.test("Initialization - min/max type", function (assert) {
var pqMax = new priority_queue("max");
assert.ok(pqMax.bh.type === "max", "Passed!");
var pqMin = new priority_queue("min");
assert.ok(pqMin.bh.type === "min", "Passed!");
});
QUnit.test("Initialization - heap capacity and size", function (assert) {
var pq = new priority_queue();
assert.ok(pq.bh.heap.length === 10, "Passed!");
assert.ok(pq.bh.current_size === 0, "Passed!");
});
QUnit.test("Enqueue element - current size is 1", function (assert) {
var pq = new priority_queue();
pq.enqueue({ priority: 13, val: "Mexico" });
assert.ok(pq.bh.heap.length === 10, "Passed!");
assert.ok(pq.bh.current_size === 1, "Passed!");
});
QUnit.test("Enqueue element - current size is 15, capacity doubles", function (assert) {
var pq = new priority_queue();
for (var i = 0; i < 15; i++){
pq.enqueue({ priority: i, val: i.toString() });
}
assert.ok(pq.bh.heap.length === 20, "Passed!");
assert.ok(pq.bh.current_size === 15, "Passed!");
});
QUnit.test("Dequeue element - current size is 1, capacity is 10", function (assert) {
var pq = new priority_queue();
pq.enqueue({ priority: 13, val: "Mexico" });
var element = pq.dequeue();
assert.ok(element.priority === 13, "Passed!");
assert.ok(element.val === "Mexico", "Passed!");
assert.ok(pq.bh.heap.length === 10, "Passed!");
assert.ok(pq.bh.current_size === 0, "Passed!");
});
QUnit.test("Dequeue elements - element with lowest priority is always at the root", function (assert) {
var pq = new priority_queue();
pq.enqueue({ priority: 13, val: "Mexico" });
pq.enqueue({ priority: 21, val: "Belgium" });
pq.enqueue({ priority: 16, val: "Italy" });
pq.enqueue({ priority: 24, val: "USA" });
pq.enqueue({ priority: 31, val: "Canada" });
pq.enqueue({ priority: 19, val: "France" });
pq.enqueue({ priority: 68, val: "Holland" });
pq.enqueue({ priority: 65, val: "Germany" });
pq.enqueue({ priority: 26, val: "China" });
pq.enqueue({ priority: 11, val: "Russia" });
pq.enqueue({ priority: 2, val: "Malaysia" });
assert.ok(pq.bh.current_size === 11, "Passed!");
var root;
root = pq.dequeue();
assert.ok(root.priority === 2, "Passed!");
assert.ok(root.val === "Malaysia", "Passed!");
root = pq.dequeue();
assert.ok(root.priority === 11, "Passed!");
assert.ok(root.val === "Russia", "Passed!");
root = pq.dequeue();
assert.ok(root.priority === 13, "Passed!");
assert.ok(root.val === "Mexico", "Passed!");
root = pq.dequeue();
assert.ok(root.priority === 16, "Passed!");
assert.ok(root.val === "Italy", "Passed!");
root = pq.dequeue();
assert.ok(root.priority === 19, "Passed!");
assert.ok(root.val === "France", "Passed!");
root = pq.dequeue();
assert.ok(root.priority === 21, "Passed!");
assert.ok(root.val === "Belgium", "Passed!");
root = pq.dequeue();
assert.ok(root.priority === 24, "Passed!");
assert.ok(root.val === "USA", "Passed!");
root = pq.dequeue();
assert.ok(root.priority === 26, "Passed!");
assert.ok(root.val === "China", "Passed!");
root = pq.dequeue();
assert.ok(root.priority === 31, "Passed!");
assert.ok(root.val === "Canada", "Passed!");
root = pq.dequeue();
assert.ok(root.priority === 65, "Passed!");
assert.ok(root.val === "Germany", "Passed!");
root = pq.dequeue();
assert.ok(root.priority === 68, "Passed!");
assert.ok(root.val === "Holland", "Passed!");
});
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment