Operations in a Priority Queue
A priority queue supports the following operations:
 enqueue(): It inserts new data into the queue.
 Dequeue (): It removes the data with the highest priority from the queue.
 Peek ()/top(): It returns the element having the highest priority in the queue.
Different ways for the Implementation of Priority Queues
We can implement the priority queues in several ways. Let’s see some of the possible options 
 Unordered Array Implementation: Elements are inserted into the array without bothering the order. Deletions are performed by searching the minimum or maximum and deleting.
 Unordered List Implementation: It is similar to array implementation but instead of array linked lists are used.
 Ordered Array Implementation: Elements are inserted into the array in sorted order based on the key field. Deletions are performed only at one end of the array.
 Ordered list implementation: Elements are inserted into the list in sorted order based on the key field. Deletions are performed at only one end, hence preserving the status of the priority queue. All other functionalities associated with a linked list ADT are performed without modification.
 Binary Search Trees Implementation: Insertion and deletions are performed in a way such that the property of BST is reserved. Both the operations take O(logn) time on average and O(n) in the worst case.
 Balanced Binary Search Trees Implementation: Insertion and deletions are performed such that the property of BST is reserved and the balancing factor of each node is 1, 0, or 1. Both operations take O(logn) time.
Comparing Implementations
Implementation of Priority Queue using Array
One of the most basic ways of implementing a priority queue is using an array.
So, every element of the array will store the following information 
 Value of the element

Priority of the element
Steps of the implementation 
 We will define a structure with two members  Value and Priority.
 Declare an array of structure having a fixed size maxSize.

Define a variable size which will determine the size of the priority queue at any instance. Initially, size=1 indicates that the queue is empty.
Let’s see how to implement all the operations on a priority queue 

enqueue(): To enqueue a new element, increment the size by 1. If size is less than maxSize, then initialize the arr[index] with the value and priority of the new element. If size exceeds the maxSize, then return.

dequeue(): It removes the element with the highest priority. So, define two variables index and highestPriority and iterate over the entire array elements. The variable index stores the index of the element having the highest priority so far, and the variable highestPriority stores the priority of arr[index].
At the end of the iteration, since we need to delete the element with the highest priority, so left shift all the elements after the position “index” by one position and finally decrement size by 1.

peek()/top(): It just returns the element with the highest priority. So, define two variables index and highestPriority and iterate over the entire array elements. The variable index stores the index of the element having the highest priority so far and the variable highestPriority stores the priority of arr[index].
Let’s see the code implementation which is very simple along with the analysis of time and space complexity in the next section.
C++ Implementation
/*C++ code to implement a priority queue using an array*/
#include <bits/stdc++.h>
using namespace std;
#define maxSize 1000
struct priorityQueueElem
{
int value;
int priority;
};
priorityQueueElem priotyQ[maxSize];
int size = 1;
void enqueue(int value, int priority)
{
size++;
if (size > maxSize)
{
cout << "Maximum number of elements that can be stored is exceeded\n";
return;
}
priotyQ[size].value = value;
priotyQ[size].priority = priority;
}
int peek()
{
int highestPriority = INT_MIN;
int index = 1;
for (int i = 0; i <= size; i++)
{
if (highestPriority == priotyQ[i].priority && index > 1 && priotyQ[index].value < priotyQ[i].value)
{
highestPriority = priotyQ[i].priority;
index = i;
}
else if (highestPriority < priotyQ[i].priority)
{
highestPriority = priotyQ[i].priority;
index = i;
}
}
return index;
}
void dequeue()
{
int index = peek();
for (int i = index; i < size; i++)
{
// left shift all elements by one
priotyQ[i] = priotyQ[i + 1];
}
size;
}
int main()
{
int n = 5;
int arr[n] = {100, 66, 54, 48, 32};
for (int i = 0; i < n; i++)
{
enqueue(arr[i], arr[i]);
}
int index = peek();
cout << priotyQ[index].value << endl;
dequeue();
index = peek();
cout << priotyQ[index].value << endl;
dequeue();
index = peek();
cout << priotyQ[index].value << endl;
return 0;
}
Output
100
66
54
Complexity Analysis
Time Complexity
 Enqueue  O(1), as we just append the new element to the end of the array.
 Dequeue  O(n), first we find the index of the highest priority element which takes O(n) time and then we shift the elements after the peek element to the left which also takes O(n) time. Hence, total time complexity becomes O(n).
 Peek  O(n), as to find the element with the highest priority we need to iterate over all the elements in the array so time complexity becomes O(n).
Space Complexity
O(n), where n is the maximum number of elements that can be stored in the priority queue.
Read about Application of Queue in Data Structure here.
Frequently Asked Questions
What are some of the applications of the priority queue?
It is used in the Huffman coding algorithm in the form of a minheap. Dijkstra’s algorithm also uses a priority queue to find the shortest paths. The operating system handles interruptions with the help of a priority queue.
What data structures can be used to implement the priority queue?
Priority Queues can be implemented by using arrays, heaps, BSTs, and linked lists. The most efficient of them is using heaps.
Conclusion
In this article, we learned all about priority queues. We started with an introduction followed by an example from a realworld scenario to understand better.
In this article, we learned the implementation using an array but there are many other ways too.
Now, that you know how to implement a priority queue, some of the problems you must practice to make your understanding crystal clear are
To learn priority queues from scratch you can check out this course on Introduction to Priority Queues.
Do check out the amazing Priority Queues & Heaps Notes in the Guided Paths section especially curated for you to learn the concepts in one of the most intuitive and practical ways along with some of the Top Array Coding Interview Questions to test your grasp of Array Data Structure.
Are you planning to ace the interviews of reputed productbased companies like Amazon, Google, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests and Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.