Priority Queue and Its implementation

A priority queue is an abstract data type which is like a regular queue with some additional property i.e. 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.

Summary

1) Every item has a priority associated with it.

2) An element with high priority is dequeued before an element with low priority.

3) If two elements have the same priority, they are served according to their order in the queue.

Priority queue Operations

insert(item, priority): Inserts an item with given priority.

getHighestPriority(): Returns the highest priority item.

deleteHighestPriority(): Removes the highest priority item.

Insert

This operation can be implemented by adding an item at end of array in O(1) time.

getHighestPriority

This operation can be implemented by linearly searching the highest priority item in an array. This operation takes O(n) time.

deleteHighestPriority

This operation can be implemented by first linearly searching an item, then removing the item by moving all subsequent items one position back.

How to implement priority queue?

Using Array: An Item type array can be used to store the heap elements.

class Item {

   int item;

   int priority;

}

insert() operation can be implemented by adding an item at end of array in O(1) time.

getHighestPriority() operation can be implemented by linearly searching the highest priority item in the array. This operation takes O(n) time.

deleteHighestPriority() operation can be implemented by first linearly searching an item, then removing the item by moving all subsequent items one position back.

Using Linked List: Advantage with the linked list while deleting the Highest Priority element. This operation can be more efficient as we don’t have to move items, unlike an array based implementation. The time complexity of all other operations will remain same as an array.

Using Heaps

Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked list.

In a Binary Heap, getHighestPriority() can be implemented in O(1) time, insert() can be implemented in O(logn) time and deleteHighestPriority() can also be implemented in O(logn) time.