-
Notifications
You must be signed in to change notification settings - Fork 55
Priority Queue
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.
A priority queue is not a heap. 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.
Wikipedia
var queue = new PriorityQueue(); //an empty priority queueThis method returns an iterator for scanning the queue. The iterator is useful in order to get a full decoupling in your classes. This avoid, to the class that uses the iterator, to know what type of data structure stores the data.
var queue = new PriorityQueue();
var it = queue.getIterator();
for(it.first(); !it.isDone(); it.next()) {
var item = it.getItem();
//do something
}The iterator starts from the head of the queue.
This method enqueue the item at the tail of the queue of the items with the same priority. The item could be whatever you want.
var queue = new PriorityQueue();
queue.enqueue(0, 4); //queue contains (from the head) 4
queue.enqueue(2, 2); //queue contains (from the head) 2, 4
queue.enqueue(1, 7); //queue contains (from the head) 2, 7, 4
queue.enqueue(1, 6); //queue contains (from the head) 2, 7, 6, 4This method enqueue the items at the head of the queue of the items with the same priority. The items could be whatever you want.
var queue = new PriorityQueue();
queue.multiEnqueue(0, [2, 5]); //queue contains (from the head) 2, 5
queue.multiEnqueue(2, [6, 3]); //queue contains (from the head) 6, 3, 2, 5
queue.multiEnqueue(1, [7, 8]); //queue contains (from the head) 6, 3, 7, 8, 2, 5
queue.multiEnqueue(1, [9, 0]); //queue contains (from the head) 6, 3, 7, 8, 9, 0, 2, 5This method remove the item at the head of the queue. The item is returned.
var queue = new PriorityQueue();
queue.enqueue(1, 4);
queue.enqueue(0, 2);
queue.dequeue(); //4 and queue contains 2m: the number of items with the maximum priority. In this case the method require to restore indexes of the array that mantains the items of the queue.
This method removes the first times items at the head of the queue. The items are returned as an array.
var queue = new PriorityQueue();
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
queue.multiDequeue(2); //[6, 8] and queue contains (from the head) 4, 2This method takes the item at the head of the queue without removing it.
var queue = new PriorityQueue();
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
queue.peek(); //6 and queue contains (from the head) 6, 8, 4, 2This method removes the first length items starting from the position index of the queue. The items aren't returned. The length parameter could be omitted. In that case, will be removed only the item at the position index.
var queue = new PriorityQueue();
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
queue.enqueue(-1, 7);
queue.remove(1, 2); //queue contains (from the head) 6, 2, 7
queue.remove(1); //queue contains (from the head) 6, 7This method empty the queue.
var queue= new PriorityQueue();
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
queue.clear(); //the queue is emptyThis method checks if the queue contains some items related to the priority to find.
var queue = new Queue();
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
queue.containsPriority(2); //true
queue.containsPriority(6); //falseThis method execute the callback function for each item stored in the queue. The callback must accept the item the iteration is working on. The callback must also return a value to assign to the item.
var queue = new PriorityQueue();
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
var callback = function(item) { //this function returns the square for each item
return item * item;
};
queue.execute(callback); //queue contains (from the head) 36, 64, 16, 4In this example we deal with more complex items.
var queue = new PriorityQueue();
queue.enqueue(1, 0);
queue.enqueue(0, 1);
var callback = function(item) { //this function encapsulate each item into an object
return {x: item, y: item + 2};
};
queue.execute(callback); //queue contains (from the head) {x: 0, y: 2}, {x: 1, y: 3}This method returns the item at position index starting from the head of the queue. So index 0 will be for the item having the maximum priority, 1 is for the second and so on.
var queue = new PriorityQueue();
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
queue.getItem(0); //6
queue.getItem(1); //8This method returns the items stored in the queue. This method doesn't store also the priority of the item.
var queue = new PriorityQueue();
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
queue.getItems(); //[6, 2, 4, 0]This method returns a queue without priority with the items of this queue.
var queue = new PriorityQueue();
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
queue.toQueue(); //queue contains (from the head) 6, 8, 4, 2This method returns the length of the queue so the number of items stored.
var queue = new PriorityQueue();
queue.getLength() //0 - the queue is empty
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
queue.getLength(); //4This method checks if the queue is empty or not.
var queue = new PriorityQueue();
queue.isEmpty() //true
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
queue.isEmpty(); //falseThis method returns all the items that satisfies the condition represented by the callback. The callback must accept the item the iteration is working on. The method starts from the head of the queue.
var queue = new PriorityQueue();
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
var callback = function(item) { //this function checks if the item is lower than 4 or greater than 6
return item < 4 || item > 6;
};
queue.filter(callback); //[2, 8];In this example we deal with more complex items.
var itemA = {parent: null, item: 0};
var itemB = {parent: itemA, item: 1};
var itemC = {parent: itemB, item: 2};
var itemD = {parent: null, item: 3};
var queue = new PriorityQueue();
queue.enqueue(2, itemB);
queue.enqueue(1, itemC);
queue.enqueue(3, itemA);
queue.enqueue(0, itemD);
var callback = function(item) { //this function checks if itemA is in the same hierarchy of the item
while(item.parent || item === itemA)
item = item.parent;
return item === itemA;
};
queue.filter(callback); //[itemC, itemB, itemA]This method change the priority of the item at position index starting from the head of the queue.
var queue = new PriorityQueue();
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2); //queue contains (from the head) 6, 8, 4, 2
queue.changePriority(2, 4); //queue contains (from the head) 4, 6, 8, 2
queue.changePriority(2, -1); //queue contains (from the head) 4, 6, 2, 8This method returns a clone of the queue. The items are cloned only if there's a method clone() to invoke, otherwise they will be shared with the old queue. This problem there is not if items are not object.
var queue = new PriorityQueue();
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(3, 6);
queue.enqueue(0, 2);
var clone = queue.clone(); //clone contains (from the head) 6, 8, 4, 2This method returns a clone of the queue containing only one copy of the same item. The items are cloned only if there's a method cloneDistinct() to invoke or at least a method clone(), otherwise they will be shared with the old queue. This problem there is not if items are not object.
var queue = new PriorityQueue();
queue.enqueue(6, 2);
queue.enqueue(5, 8);
queue.enqueue(4, 4);
queue.enqueue(3, 6);
queue.enqueue(2, 8);
queue.enqueue(1, 4);
queue.enqueue(0, 2);
queue.enqueue(-1, 6);
var clone = queue.cloneDistinct(); //clone contains (from the head) 2, 8, 4, 6m: the number of distinct elements stored in the queue. The time required depends strongly from the number of items duplicated. If the number of items duplicated is very high, then m tend to be near 1 (when the queue contains only one distinct item) so complexity will be O(n). If the number of items duplicated is very low, then m tend to be near n (when the queue doesn't contain any duplicated items) so complexity will be O(n2).