Priority Queues

Introduction

You have N distinct jobs to process, and you are given the responsibility to schedule them on the only available job processor.
New jobs keeps on getting added into the set of available jobs. Not all the jobs are to be executed as they come.
There might be few which needs to be executed immediately and few can be postponed for some time.

You have an efficiently algorithm to decide the priority of an incoming job. The task at hand is as follows:

  1. To schedule available jobs based on the priority assigned to them.
  2. Add new jobs to the set after assigning a priority to it.

What are the choices available to us for the scheduling?

The first option which comes to mind is maintaining a reversely sorted linked list of jobs (sorted with priority).

  • Each time a new job arrives, we insert it into the sorted linked list. In worst case, we end up travelling the complete linked list to insert a new job (job with minimum priority). It is O(N), where N is the current size of the linked list.
  • Each time we need to find the max priority job for scheduling, its just removal of head and takes a constant running time O(1).
  • What if we want to change the priority of an already existing job?
    • It takes removal of the job from the current position in the linked list and insertion at a different position.
    • Which again is a O(N) operation.

If there are a lot of jobs coming in (which actually is the use case of scheduler), then the running time of the arrangement will be dominated by O(N).

The second option would be using a max heap, where the key of the heap is the priority.

Hence, the max priority will always we at the root and can be removed immediately, followed by a heapify process which takes O(logN) time. [Refer my previous posts on Heaps]

The insertion of a new job will take O(logN) time because its just an insertion in the max heap.

Changing the priority again will take a O(logN) operation as it is a delegation to the increase key operation of the max heap (this only allows increasing the priority, we can always write a method in the max heap to decrease the priority).

Solution

As we saw that max heaps can do the job better, so let us try and create some API with our already acquired knowledge of Max Heap.

So, if you already followed the previous posts with Heaps, it would be really easy to implement the PriorityQueue.

What are some other use cases of PriorityQueue?

let us say that we are designing a event simulation system, where we already have couple of events which will fire at certain time. Now, the event which has a lesser time will fire early.

There may be a possibility that the event upon completion generates other events which must fire at a future time.

These kind of scenarios can again be handled with a priority queue. With a small change that the priority queue now has time as the priority and the lesser time has a higher priority.

This can be easily implemented using a min heap.

Side Note:

This is not the only way to implement a priority queue, but yes this is one of the good ways to implement it which ensures a O(logN) running time for all the basic operations. A few modifications to this can be done to improve the running time and bring it down.

There are many more usages of a priority queue and that is an awesome data structure too implement and easy as well.  In case you found something missing or complicated, please let me know in comments so that I can update/correct it.

Stay subscribed as I will be posting new interview and practice problems using priority queues.