A binary heap-based priority queue, written in JavaScript, supporting only unique values but allowing O(log n) remove and update.

heap_priority_queue.js

(function(global) {

    /**
     * Constructor for a binary heap-based Priority Queue.
     * Because this priority queue supports the remove and update operations in
     *   O(log n) time, all values must be unique and usable as object keys.
     * Weird things may happen if you insert different types, or insert more
     *   than 2**31 objects. Don't use this for anything serious.
     */
    function PriorityQueue(initial_list, cmp_func) {
        this._heap = [];
        this._cmp_func = cmp_func || PriorityQueue.DEFAULT_COMPARATOR;
        this._pos_map = Object.create(null);

        if (initial_list) {
            // insert elements into this._heap and this._pos_map
            this._heap = [].slice.call(initial_list, 0).map(function(value, i) {
                if (value in this._pos_map) {
                    throw new Error("Priority queue already contains value " + value);
                }
                this._pos_map[value] = i;
                return { priority: value, value: value };
            }.bind(this));

            // convert to heap
            this._heapify();
        }
    }


    PriorityQueue.DEFAULT_COMPARATOR = function(a, b) {
        if      (a < b) return -1;
        else if (a > b) return 1;
        else            return 0;
    };


    PriorityQueue.prototype = {

        /**
         * Returns the length of the priority queue.
         */
        get length() {
            return this._heap.length;
        },


        /**
         * Returns whether the priority queue is empty.
         */
        get isEmpty() {
            return this._heap.length == 0;
        },


        /**
         * Checks whether element is in the priority queue.
         */
        contains: function(value) {
            return value in this._pos_map;
        },


        /**
         * Returns the currently assigned priority of an element in the priority queue.
         */
        get_priority: function(value) {
            if (!this.contains(value)) {
                throw new Error("Priority queue does not contain value " + value);
            }
            return this._pos_map[value].priority;
        },


        /**
         * Adds an element to the priority queue with given priority.
         * If no priority is provided, the object's value is used as the priority.
         */
        push: function(value, priority) {
            var obj = {
                priority: priority || value,  // just order by value
                value: value
            };

            // insert obj into _value_map
            if (value in this._pos_map) {
                throw new Error("Priority queue already contains value " + value);
            }
            this._pos_map[value] = this._heap.length;

            // insert into heap
            this._heap.push(obj);

            // bubble up element
            this._siftDown(this._heap.length - 1);
        },


        /**
         * Updates the priority of an element in the priority queue.
         */
        update: function(value, priority) {
            if (!this.contains(value)) {
                throw new Error("Priority queue does not contain value " + value);
            }

            // find object in map
            var pos = this._pos_map[value];
            var obj = this._heap[pos];

            if (obj.value != value) {
                throw new Error("Assertion error");
            }

            // update priority
            obj.priority = priority;

            // move down to bottom and back up
            this._siftUp(pos);
        },


        /**
         * Removes an element from the priority queue.
         */
        remove: function(value) {
            if (!this.contains(value)) {
                throw new Error("Priority queue does not contain value " + value);
            }

            // find object in map
            var pos = this._pos_map[value];
            var obj = this._heap[pos];
            
            if (obj.value != value) {
                throw new Error("Assertion error");
            }

            // move last element into pos
            var last = this._heap.pop();

            if (pos != this._heap.length) {
                // move last element to pos
                this._heap[pos] = last;
                this._pos_map[last.value] = pos;

                // move down element
                this._siftUp(pos);
            }

            // remove from value_map
            delete this._pos_map[obj.value];

            return obj.value;
        },


        /**
         * Returns the element that would be removed by pop(), or undefined
         * if the priority queue is empty.
         */
        peek: function() {
            return this._heap[0];
        },


        /**
         * Remove an element from the priority queue. Throws an exception if
         * the priority queue is empty.
         */
        pop: function() {
            if (this._heap.length == 0) {
                throw new Error("Priority queue is empty");
            }

            // remove last element
            var obj = this._heap[0];
            var last = this._heap.pop();

            if (this._heap.length != 0) {
                // move last element to top
                this._heap[0] = last;
                this._pos_map[last.value] = 0;

                // move down top element
                this._siftUp(0);
            }

            // remove from _value_map
            delete this._pos_map[obj.value];

            return obj.value;
        },


        /**
         * Comparator function.
         */
        _cmp: function(a, b) {
            var cmp = this._cmp_func(a.priority, b.priority);
            if (typeof cmp != "number" || isNaN(cmp)) {
                throw new TypeError("Comparison function returned illegal value: " + cmp);
            }
            return cmp;
        },


        /**
         * Transforms a list into a heap.
         */
        _heapify: function() {
            var last = (this._heap.length >>> 1) - 1;
            var i;
            for (i = last; i >= 0; i--) {
                this._siftUp(i);
            }
        },


        /**
         * Performs the sift-up operation.
         */
        _siftUp: function(pos) {
            var item = this._heap[pos];
            var child = 2*pos + 1;

            // move value all the way to the bottom
            while (child < this._heap.length) {
                // use right child if smaller
                if (child+1 < this._heap.length &&
                    this._cmp(this._heap[child+1], this._heap[child]) < 0)
                {
                    child = child+1;
                }
                // shift child up
                this._heap[pos] = this._heap[child];
                this._pos_map[this._heap[child].value] = pos;
                pos = child;
                child = 2*pos + 1;
            }

            this._heap[pos] = item;
            this._pos_map[item.value] = pos;

            // move value back up from bottom
            this._siftDown(pos);
        },


        /**
         * Performs the sift-down operation.
         */
        _siftDown: function(pos) {
            var item = this._heap[pos];
            var parent = (pos - 1) >>> 1;

            // move value to top or until heap invariant is satisfied 
            while (pos > 0 && this._cmp(item, this._heap[parent]) < 0) {
                // shift parent down
                this._heap[pos] = this._heap[parent];
                this._pos_map[this._heap[parent].value] = pos;
                pos = parent;
                parent = (pos - 1) >>> 1;
            }

            this._heap[pos] = item;
            this._pos_map[item.value] = pos;
        }
    };


    global.HeapPriorityQueue = PriorityQueue;

}(this));