A priority queue is a collection of elements such that each element has been assigned a priority and the order in which elements are deleted and processed comes from the following rules:
- An element of higher priority is processed before any element of lower priority.
- If two elements has same priority then they are processed according to the order in which they were added to the queue.
The best application of priority queue is observed in CPU scheduling.
- The jobs which have higher priority are processed first.
- If the priority of two jobs is same this jobs are processed according to their
position in queue. - A short job is given higher priority over the longer one.
Types of priority queues
- Ascending priority queue(min priority queue)
An ascending priority queue is a collection of items into which items can be inserted arbitrarily but from which only the smallest item can be removed.
- Descending priority queue (max priority queue)
An descending priority queue is a collection of items into which items can be inserted
arbitrarily but from which only the largest item can be removed.
Basic Operations
insert / enqueue − add an item to the rear of the queue.
remove / dequeue − remove an item from the front of the queue.
Priority Queue Representation
Priority Queue is more specialized data structure than Queue. In Priority queue items are ordered by key value so that item with the lowest value of key is at front and item with the highest value of key is at rear or vice versa. So we’re assigned priority to item based on its key value. Lower the value, higher the priority. Following are the principal methods of a Priority Queue.
Priority Queue Declaration
#define MAXQUEUE 10 /* size of the queue items*/ struct pqueue
{
int front;
int rear;
int items[MAXQUEUE];
};
struct pqueue *pq;
The priority queue ADT
A ascending priority queue of elements of type T is a finite sequence of elements of T together with the operations:
- MakeEmpty(p): Create an empty priority queue p
- Empty(p): Determine if the priority queue p is empty or not
- Insert(p,x): Add element x on the priority queue p
- DeleteMin(p): If the priority queue p is not empty, remove the minimum element of the quque and return it.
- FindMin(p): Retrieve the minimum element of the priority queue p.
Array implementation of priority queue
- Unordered array implementation
- To insert an item, insert it at the rear end of the queue.
- To delete an item, find the position of the minimum element and
- To insert an item, insert it at the rear end of the queue.
-
- Either Mark it as deleted (lazy deletion) or
-
-
- shift all elements past the deleted element by one position and then decrement rear
-
- Ordered array implementation
-
Set the front as the position of the smallest element and the rear as the position of the largest
element. - To insert an element, locate the proper position of the new element and shift preceding or succeeding elements by one position.
- To delete the minimum element, increment the front position.
-
Application of Priority Queue
- Artificial intelligence: A* search
- Operating systems: load balancing, interrupt handling
- Time sharing computer system: the set of tasks waiting for the CPU forms a priority queue
REFRENCES:
- http://www.tutorialspoint.com/data_structures_algorithms/priority_queue.htm
- http://www.learn-c.org/en/Pointer_Arithmetics
- http://stackoverflow.com/questions/18049847/when-would-i-use-a-priority-queue
- Data Structure Notes by Bhupendra Saud
For codes: github