Priority Queue

A queue is FIFO datastructure which means objects added first will be accessed first. Priority queue adds an element of priority with each object added to queue. And when elements are accessed they will be accessed based on this priority in increasing (min- priority queue) or decreasing (max- priority queue).

There are multiple ways wo implement priority queue, basic one is to use queue, and just add priorit elelemnt. A queue has insertion and deletion operation at Order of 1 as elements are added and removed from front. But in case of priority queue, though we will add elements at front, but delete/ fetch based on priority, so we will need to traverse the whole list, hence O(N).

Start->Node1{obj, P3}->Node1{obj, P4}->Node1{obj, P1}->Node1{obj, P2}->End

Another, more efficient way to implement priority queue is using heap data structure.

Read here about – http://kamalmeet.com/algorithms/heap-data-structure/

As heap data structure automatically maintains priority (Min heap – Min priority queye/ Max heap – Max priority queue), it fits best to implement priority queue. As both insertion and deletion of objects in heap is O(log N) operation, same is true for priority queue implemented through heap.

Leave a Reply

Your email address will not be published. Required fields are marked *