🎉 JointJS has new documentation! 🥳
🎉 JointJS has new documentation! 🥳
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.
Include joint.alg.priorityQueue.js file into your HTML:
<script src="joint.alg.priorityQueue.js"></script>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
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 decreaseKeyalg.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| 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.
|