jdecuyper/priority-queue.js

## priority-queue.js
<!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>
	<!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>