data-structurespriority-queueheap

How to use built in priority queue in javascript?


How can we use built in priority queue in javascript

In chrome I am not able to run built in pq in javascript


Solution

  • There is nothing "built in" in JavaScript that bears the name priority queue. The native thing that comes closest is a plain object with array-index keys.

    That comes with some limitations:

    • The keys of the priority queue have to be unsigned integers in the 32-bit range
    • The priority queue cannot hold two items with the same key unless you add additional logic to deal with that.

    Here is how that would work:

    function pqInsert(pq, key, value) {
        if (String(Math.abs(+key | 0)) != String(key)) throw "Key must be unsigned 32 bit integer";
        if (pq[key] !== undefined) throw "Duplicate key";
        pq[key] = value;
    }
    
    function pqLeastKey(pq) {
        for (const key in pq) { // Iterate numeric keys in order
            return key; // Exit in first iteration
        }
    }
    
    function pqExtract(pq) {
        const key = pqLeastKey(pq);
        const value = pq[key]; // Get value of least key
        delete pq[key]; // Remove it
        return [key, value];
    }
    
    const pq = {};
    
    // I/O handling
    const [keyInput, valueInput, addButton, removeButton, br, output] =
              document.body.children;
    addButton.onclick = () => {
        pqInsert(pq, keyInput.value, valueInput.value);
        keyInput.value = valueInput.value = "";
        output.textContent = JSON.stringify(pq, null, 2);
    }
    removeButton.onclick = () => {
        [keyInput.value, valueInput.value] = pqExtract(pq);
        output.textContent = JSON.stringify(pq, null, 2);
    };
    input { width: 5em }
    Key: <input type="number" min="0"> Value: <input> <button>Add</button>
    <button>Extract minimum</button><br>
    Queue: <pre>{}</pre>

    That's as close as you can get to a native priority queue behaviour in JavaScript. Alternatively, you can of course add a library, or throw your own implementation of a priority queue. For instance, at Efficient way to implement Priority Queue in Javascript? you'll find some implementations. I also posted my heap implementation there.