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)
• peak: 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.

constructor

constructor(opt?: PriorityQueueOptions);

The joint.alg.PriorityQueue constructor accepts the following parameters:

data

[optional] 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.

comparator

[optional] 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.

Methods

isEmpty()

priorityQueue.isEmpty(): boolean;

Return true if the priority queue is empty, false otherwise.

insert()

priorityQueue.insert(priority: number, value: any, id?: number | string): void;

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()

priorityQueue.peek(): any;

Return the value of an item with the highest priority.

peekPriority()

priorityQueue.peekPriority(): number;

Return the highest priority in the queue.

remove()

priorityQueue.remove(): any;

Return the value of an item with the highest priority and remove the item from the queue.

updatePriority()

priorityQueue.updatePriority(id: number | string, priority: number): void;

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.

Types

Options

interface PriorityQueueOptions {
    comparator?: (a: number, b: number) => number;
    data: Array<any>
}