Priority Queue

Definition

In computer science/data structures, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods.

Source: Wikipedia

Implementation details

This implementation of the priority queue uses the behavior of a min-priority-queue, where items with lower priorities are returned first, and it's implemented on top of a MinHeap

Code: https://github.com/felipernb/algorithms.js/blob/master/data_structures/priority_queue.js

Tests: https://github.com/felipernb/algorithms.js/blob/master/test/data_structures/priority_queue.js

How to use

Import

var PriorityQueue = require('algorithms').DataStructure.PriorityQueue;

Initialization

// Empty priority queue
var q = new PriorityQueue();

// Pre-populated priority queue
var q = new PriorityQueue({a: 1, b:10, c: 5});

PriorityQueue.prototype.insert(item, priority)

Insert the element into the priority queue, in O(lg n)

var q = new PriorityQueue();
q.insert('a', 4);
q.insert('b', 10);
q.insert('c', 5);

/**
 * Will give you a queue that can be represented like:
 * ↳ a -> b -> c
 */

PriorityQueue.prototype.isEmpty()

Boolean indicating whether the queue is empty

var q = new PriorityQueue();
q.isEmpty(); // true
q.insert('a', 4);
q.isEmpty(); // false

PriorityQueue.prototype.extract()

Extracts the element with minimum priority from the Queue

var q = new PriorityQueue();
q.insert('a', 4);
q.insert('b', 10);
q.insert('c', 5);

q.extract(); // a
q.extract(); // c
q.extract(); // b

PriorityQueue.prototype.changePriority(item, newPriority)

Changes the priority of one item in the queue

var q = new PriorityQueue();
q.insert('a', 4);
q.insert('b', 10);
q.insert('c', 5);

q.changePriority(b, 1);

q.extract(); // b
q.extract(); // a
q.extract(); // c