- Notifications
You must be signed in to change notification settings - Fork55
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
varqueue=newPriorityQueue();//an empty priority queue
This 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.
varqueue=newPriorityQueue();varit=queue.getIterator();for(it.first();!it.isDone();it.next()){varitem=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.
varqueue=newPriorityQueue();queue.enqueue(0,4);//queue contains (from the head) 4queue.enqueue(2,2);//queue contains (from the head) 2, 4queue.enqueue(1,7);//queue contains (from the head) 2, 7, 4queue.enqueue(1,6);//queue contains (from the head) 2, 7, 6, 4
This method enqueue the items at the head of the queue of the items with the same priority. The items could be whatever you want.
varqueue=newPriorityQueue();queue.multiEnqueue(0,[2,5]);//queue contains (from the head) 2, 5queue.multiEnqueue(2,[6,3]);//queue contains (from the head) 6, 3, 2, 5queue.multiEnqueue(1,[7,8]);//queue contains (from the head) 6, 3, 7, 8, 2, 5queue.multiEnqueue(1,[9,0]);//queue contains (from the head) 6, 3, 7, 8, 9, 0, 2, 5
This method remove the item at the head of the queue. The item is returned.
varqueue=newPriorityQueue();queue.enqueue(1,4);queue.enqueue(0,2);queue.dequeue();//4 and queue contains 2
m: 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.
varqueue=newPriorityQueue();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, 2
This method takes the item at the head of the queue without removing it.
varqueue=newPriorityQueue();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, 2
This 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.
varqueue=newPriorityQueue();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, 7queue.remove(1);//queue contains (from the head) 6, 7
This method empty the queue.
varqueue=newPriorityQueue();queue.enqueue(2,8);queue.enqueue(1,4);queue.enqueue(3,6);queue.enqueue(0,2);queue.clear();//the queue is empty
This method checks if the queue contains some items related to the priority to find.
varqueue=newQueue();queue.enqueue(2,8);queue.enqueue(1,4);queue.enqueue(3,6);queue.enqueue(0,2);queue.containsPriority(2);//truequeue.containsPriority(6);//false
This 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.
varqueue=newPriorityQueue();queue.enqueue(2,8);queue.enqueue(1,4);queue.enqueue(3,6);queue.enqueue(0,2);varcallback=function(item){//this function returns the square for each itemreturnitem*item;};queue.execute(callback);//queue contains (from the head) 36, 64, 16, 4
In this example we deal with more complex items.
varqueue=newPriorityQueue();queue.enqueue(1,0);queue.enqueue(0,1);varcallback=function(item){//this function encapsulate each item into an objectreturn{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.
varqueue=newPriorityQueue();queue.enqueue(2,8);queue.enqueue(1,4);queue.enqueue(3,6);queue.enqueue(0,2);queue.getItem(0);//6queue.getItem(1);//8
This method returns the items stored in the queue. This method doesn't store also the priority of the item.
varqueue=newPriorityQueue();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.
varqueue=newPriorityQueue();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, 2
This method returns the length of the queue so the number of items stored.
varqueue=newPriorityQueue();queue.getLength()//0 - the queue is emptyqueue.enqueue(2,8);queue.enqueue(1,4);queue.enqueue(3,6);queue.enqueue(0,2);queue.getLength();//4
This method checks if the queue is empty or not.
varqueue=newPriorityQueue();queue.isEmpty()//truequeue.enqueue(2,8);queue.enqueue(1,4);queue.enqueue(3,6);queue.enqueue(0,2);queue.isEmpty();//false
This 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.
varqueue=newPriorityQueue();queue.enqueue(2,8);queue.enqueue(1,4);queue.enqueue(3,6);queue.enqueue(0,2);varcallback=function(item){//this function checks if the item is lower than 4 or greater than 6returnitem<4||item>6;};queue.filter(callback);//[2, 8];
In this example we deal with more complex items.
varitemA={parent:null,item:0};varitemB={parent:itemA,item:1};varitemC={parent:itemB,item:2};varitemD={parent:null,item:3};varqueue=newPriorityQueue();queue.enqueue(2,itemB);queue.enqueue(1,itemC);queue.enqueue(3,itemA);queue.enqueue(0,itemD);varcallback=function(item){//this function checks if itemA is in the same hierarchy of the itemwhile(item.parent||item===itemA)item=item.parent;returnitem===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.
varqueue=newPriorityQueue();queue.enqueue(2,8);queue.enqueue(1,4);queue.enqueue(3,6);queue.enqueue(0,2);//queue contains (from the head) 6, 8, 4, 2queue.changePriority(2,4);//queue contains (from the head) 4, 6, 8, 2queue.changePriority(2,-1);//queue contains (from the head) 4, 6, 2, 8
This method returns a clone of the queue. The items are cloned only if there's a methodclone() to invoke, otherwise they will be shared with the old queue. This problem there is not if items are not object.
varqueue=newPriorityQueue();queue.enqueue(2,8);queue.enqueue(1,4);queue.enqueue(3,6);queue.enqueue(0,2);varclone=queue.clone();//clone contains (from the head) 6, 8, 4, 2
This method returns a clone of the queue containing only one copy of the same item. The items are cloned only if there's a methodcloneDistinct() to invoke or at least a methodclone(), otherwise they will be shared with the old queue. This problem there is not if items are not object.
varqueue=newPriorityQueue();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);varclone=queue.cloneDistinct();//clone contains (from the head) 2, 8, 4, 6
m: 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 beO(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 beO(n2).