JointJS+ PriorityQueue

You may see the name Rappid in our documentation, code and other materials. Rappid has been replaced by a new brand, JointJS+. This change has no effect on functionality. To avoid confusion, please consider Rappid and JointJS+ as synonyms. Read more here.

alg.PriorityQueue

alg.PriorityQueue is an implementation of the Priority Queue abstract data type. It is like a normal stack or queue, but where each item has assigned a priority (a number). Items with higher priority are served before items with lower priority. This implementation uses binary heap as an internal representation of the queue. The time complexity of all the methods is as follows:

  • create: O(n)
  • insert: O(log n)
  • peek: O(1)
  • peekPriority: O(1)
  • remove: O(log n)
  • isEmpty: O(1)

alg.PriorityQueue is used internally by the alg.Dijkstra algorithm for finding the shortest path in a graph. It is however useful on its own, that's why it is listed as a separate plugin.

Install

Include joint.alg.priorityQueue.js file into your HTML:

<script src="joint.alg.priorityQueue.js"></script>

Usage

The usage of alg.PriorityQueue is pretty simple. You just have to create an object of the joint.alg.PriorityQueue type. Then you can insert, remove or retrieve elements from the queue similarly as you would do with a normal JavaScript array.

var q = new joint.alg.PriorityQueue;    
q.insert(1, 'one');
q.insert(3, 'three');
q.insert(2, 'two');

q.peek()  // the first value is 'one'
q.peekPriority()  // the first priority is 1
q.remove() // the first value was 'one'
q.remove() // the second value was 'two'
q.remove() // the third value was 'three'
q.isEmpty() // true

Moreover, this implementation of the priority queue allows you to update priorities of any item that you have inserted into the queue. This is also known as the decreaseKey operation. For this to work, you have to give each item you insert into the queue a unique ID. This is because in JavaScript, objects do not have unique IDs by default. Therefore, there is no way the alg.PriorityQueue can know which item you'd like to update priority for. Here is an example of priority queue that uses the updatePriority() operation:

var q = new joint.alg.PriorityQueue;
q.insert(1, 'one', 'id1');
q.insert(3, 'three', 'id3');
q.insert(2, 'two', 'id2');

q.peek() // the first value is 'one'
q.updatePriority('id1', 5);
q.peek() // now the first value is 'two'
q.updatePriority('id1', 1);
q.peek() // the first value 'one' got again back to the top

API

joint.alg.PriorityQueue([opt]) Create a priority queue object. If opt.data array is passed, it must be an array of items of the form { priority: Number, value: Object }. In this case, the priority queue will be initialized with this array. It's like calling insert(priority, value) for each item of this array. opt.comparator can optionally be a function that will be used to compare two priorities. The signature of this function is function(a, b). The function should return a value less then 0 if priority a is lower than priority b, value equal to 0 if the priorities are the same and value bigger than 0 if priority a is higher than priority b. The comparator function defaults to: function(a, b) { return a - b }. This function effectively allows you to use any object as a priority in which case it is on you to tell the priority queue how to compare two priorities.
isEmpty() Return true if the priority queue is empty, false otherwise.
insert(priority, value [, id]) Insert a value with priority to the queue. Optionally pass a unique id of this item. Passing unique IDs for each item you insert allows you to use the updatePriority() operation. See the Usage section for details.
peek() Return the value of an item with the highest priority.
peekPriority() Return the highest priority in the queue.
remove() Return the value of an item with the highest priority and remove the item from the queue.
updatePriority(id, priority) Update priority of an item identified by a unique id. You can only use this operation if all the items you inserted to the queue had a unique ID assigned. See the Usage section for details.