priority queue and its applications

Priority queue is a data structure like queue. Before talking about priority queue, Let us just briefly talk about queue first.

Queue is a First In First Out (FIFO) or Last In Last Out (LILO) Data structure which means that you will retrieve the elements/Items in the same order in which they are inserted. Queue is motivated from our real life. We see queue in our real life at many places, at railway station, In temples, in Office/Hostel Mess etc etc... Person who enters the queue first is served first.

Priority queue is little different from queue. Instead of first come first serve policy, it serves the items based on their priority. Item with highest priority will be served first irrespective of when it was entered in the queue. Each item/element that enters the queue has a priority assigned to it. E.g.

1,2,3,10,4,6 is entered in the queue in the order from left to right and say higher the number, higher is the priority.

When item is retrieved from the queue, it will return 10 although 1 was entered first in the queue.

Now question comes why it was even discovered? How is it useful?

Priority queue is also inspired from our daily lives. Say you have multiple tasks to do at a time(cooking, cleaning, checking email, ordering vegetables and fruits). You make a list at a notepad and decide to do them in order. While working, you get a high priority task like your spouse call you to pick your child from school as she/he is busy in meeting. It is another task that you have to do but you will serve it fist since it is highest priority.

Similarly in computer science, there are many applications that needs such handling. Best example that is coming to my mind is real time operating systems.

RTOS Scheduler maintains a queue of pending task but it can not serve them in First come first serve order . It picks up task that has highest priority.

E.g. OS used in Airplanes. While operating system is doing some of its job. A job, of informing the pilot that fuel tank is going to be empty in sometime, comes. This is the job that requires highest attention. Hence scheduler will schedule this job first among all jobs.

Now we will talk briefly about its implementation.

To return the maximum element, we have two options.

• Save the items in the sorted itself i.e. As soon as item is entered in the queue, place it at its right place.
• It will increase time of adding element to O(N) from O(1) in the queue but time to retrieve element from queue will be constant O(1).
• Find the element with highest priority from queue when item has to be retrieved from queue.
• It will not affect time of adding element. It is going to be same O(1) but it will increase time of retrieving element from O(1) to O(N).

One can use any implementation that suits her/his application's need. But it is quite clear that ultimately both are gonna take N^2 time whether it is invested while adding or removing. 

So to improve the run time of your queue, heap is used which can reduce complexity to o(NlogN).