Priority Queue: Things you need to Know

Sounds familiar? but we’re going to take a closer look.

So, let's see what we’ll be getting to know from this blog.

1. What is Priority Queue?
2. Different ways to implement Priority Queue and its time complexities.
3. Characteristics of Priority Queue.
4. Types of Priority Queue?
5. Application of Priority Queue.
6. Identification of Priority Queue.
7. Solve this question using Priority Queue.
8. How to approach Questions in interview?

What is Priority Queue?

A priority Queue is a special type of queue, in which each element is associated with a priority value, and elements are served on the basis of their priority, i.e., higher priority elements are served first.

However, if element with the same priority occur, they are served according to their order in the queue.

Now how is Priority Queue different from normal Queue?

Different ways to implement Priority Queue and its time complexities

Priority Queue can be implemented using the following data structures:

• Array
• LinkedList
• Heap Data Structure
• Binary Search Tree

What are the Characteristics of a Priority Queue?

A queue is termed as a priority queue if it has the following characteristics:

• Each item has some priority associated with it.
• An item with the highest priority is moved at the front and deleted first.
• If two elements share the same priority value, then the priority queue follows the first-in-first-out principle for de queue operation.

Types of Priority Queue?

Now among all the data structures mentioned above, used to implement Priority Queue, “Heap Data Structure” is the most efficient one. Thus, we will be considering it in the rest of the blog. Before that, let's see the different types of priority queue present there:

(a) Ascending Order Priority Queue: Now ascending means the elements present in the top of priority queue are lower in value than the rest of the elements. So basically, the heap (data structure) which is used to solve this ascending order priority queue is known as minHeap.

For example, you have six numbers in the priority queue that are 4, 8, 12, 45, 35, 20. Firstly, you will arrange these numbers in ascending order. The new list is as follows: 4, 8, 12, 20. 35, 45. In this list, 4 is the smallest number. Hence, the ascending order priority queue treats number 4 as the highest priority.

In the above queue, 4 has the highest priority, and 45 has the lowest priority.

The Syntax for writing it in C++ is:

priority_queue<int, vector<int>, greater<int>>minHeap

(b) Descending Order Priority Queue: Now descending means the elements present in the top of priority queue are higher in value than the rest of the elements. So basically, the heap (data structure) which is used to solve this descending order priority queue is known as maxHeap.

For example, you have six numbers in the priority queue that are 4, 8, 12, 45, 35, 20. Firstly, you will arrange these numbers in ascending order. The new list is as follows: 45, 35, 20, 12, 8, 4. In this list, 45 is the highest number. Hence, the descending order priority queue treats number 45 as the highest priority.

In the above queue, 45 has the highest priority and 4 has the lowest priority.

The Syntax for writing it in C++ is:

priority_queue<int>maxHeap

Applications of Priority Queue

1. Data Compression: Huffman Coding Algorithm
2. Shortest Path Algorithm: Dijkstra’s Algorithm
3. Minimum Spanning Tree: Prim’s Algorithm
4. Selection Problems: find kth (smallest or largest element)
5. CPU Scheduling
6. Event driven simulation: customers in a line

Identification of Priority Queue

Now the most important question boils down to how to identify if priority queue will be used in a question or not? So, to answer this question, there is a very small trick which one can follow while solving any particular question. If a question is given with these 2 terminologies, then you can think of solving that question using priority queue:

1. Kth
2. Smallest/ Largest/ Max/ Min

If (smallest/ min) given, then use: maxHeap

if (greatest/ max) given, then use: minHeap

Solve this question using Priority Queue

Given an array and a number K where K is smaller than the size of the array. Find the K’th smallest element in the given array. Given that all array elements are distinct.

Example:

Input: vector<int>v = {4, 8, 3, 90, 13, 5}, K = 4
Output: 7

Your code is below:

The above code is written in C++ and maxHeap (descending queue) is being used since we are asked to find out the smallest element.

How to approach Questions in interview

If questions are read properly, then one can easily figure that these can be solved (ofcourse brute-force method) using sorting algorithms where the maximum time complexity we can achieve is by using merge sort (TC — O(nlog(n))) but we want to decrease the complexity more. There comes our hero — “priority_queue” which have the capability to reduce the complexity to O(nlog(k))).

Thanks for reading till the end, I hope you liked the blog :)

If so, you can clapp for it and you can connect with me on linkedin and twitter:

https://www.linkedin.com/in/sayan-maity2003/

Sayan Maity 🇦🇷 (@Sayancr777) / Twitter