Data Structures and Algorithms - Old Questions

13. What is priority queue? How it is best implemented?

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.

There are two types of priority queues they are as follows...

1. Max Priority Queue
2. Min Priority Queue

1. Max Priority Queue: In max priority queue, elements are inserted in the order in which they arrive the queue and always maximum value is removed first from the queue. For example assume that we insert in order 8, 3, 2, 5 and they are removed in the order 8, 5, 3, 2.

2. Min Priority Queue: Min Priority Queue is similar to max priority queue except removing maximum element first, we remove minimum element first in min priority queue.

Priority Queues can be implemented using common data structures like arrays, linked-lists, heaps and binary trees.