Structure of Data Item and operations
For our priority queue implementation using a linked list, the information will reside in each node along with the address to the next node. Every task will be given a priority number (priority) and a task name (data). So, every node will look like this -
It’s a good chance to revise our OOPS concepts to implement these nodes using class. Please see the code below for reference;
class Node {
// Data members of our Node class.
public:
string data;
int priority;
Node* next;
// New node constructor.
Node(string data, int priority)
{
this->data = data;
this->priority = priority;
this->next = NULL;
}
};
Let’s take a quick look at the operations we need to include in our priority queue implementation.
Functional Requirements
The priority queue implementation involves three operations: Push, Peek, and Pop.
To carry out these operations, the following functions may be useful:
- push(): Inserts the node based on its priority number.
- pop(): Deletes the node from the beginning.
- peek(): Retrieves the node present at the beginning.
- print(): To check the order of tasks and their respective priorities.
- isEmpty(): To check if the priority queue is empty.
Here, print() and isEmpty() act as helper functions to make the code less redundant and insightful. Let’s look at the procedure to understand what’s going under the hood of our priority queue implementation.
Procedure
-
isEmpty()
A priority queue will be empty in two cases. Either no data is pushed yet or our Mr. Procrastinator, Raj has popped all the tasks assigned to him. So how do we check if our priority queue is empty? If the ‘NEXT’ pointer of the ‘HEAD’ node points to NULL, then we can say that our priority queue is empty.
-
peek()
To peek at our priority queue, check the first node of the linked list. The ‘NEXT’ pointer of the ‘HEAD’ node points to the first node of the linked list. If the head is pointing to NULL, that means our priority queue is empty.
To check the first node of the linked list, we only need to access the ‘HEAD’ node, which is a constant time operation. So, the time complexity for the peek operation is O(1).
-
pop()
For pop operation, simply set the ‘NEXT’ pointer of ‘HEAD’ to the next of the first node.
Don’t forget to free the first node!
What if the priority queue is empty?
This is an edge case. If the priority queue is empty, then the ‘HEAD’ points to a NULL pointer. Trying to free a null pointer will result in a runtime error, known as a segmentation fault. So, it’s advisable to check if the priority queue is empty before performing the pop operation. Our isEmpty() function can come in handy to check the same.
Can you guess the time complexity of the pop operation?
Just as similar to the peek operation, removing the first node of the linked list (if present) requires a constant time operation. So, the time complexity is O(1) for the same.
-
push()
Keep traversing through the linked list until you find the next node with lower priority (in other words, the node with a higher priority number). Insert the newNode after your current node.
What if there’s no next node?
In that case, we have reached the end of the linked list and the newNode holds the lowest priority in the queue. Insert the newNode at the end of the linked list.
For push operations, in the worst-case scenario, we may have to traverse through the entire list as the priority of the input may be the lowest in the list. So, the time complexity becomes O(N) in the worst case.
- print()
At some point, we will need to check if our priority queue implementation is working right. Or maybe we want to check all the data items present in our priority queue. In either case, we need to print our priority queue.
To print the items of the priority queue, we need to traverse through the entire linked list. We’ll set a temporary pointer equal to the ‘HEAD’ of our data structure and keep printing the task name and its priority till we reach the end of the linked list.
How will we know if we have reached the end?
Well, if there’s no next node available we can say we have reached the end.
Traversing through the linked list is a linear-time operation. So, the time complexity for print() is O(N)
C++ Code for Reference
// Priority Queue Implementation.
#include <bits/stdc++.h>
using namespace std;
class Node {
// Data members of Node class.
public:
string data;
int priority;
Node* next;
// New node constructor.
Node(string data, int priority)
{
this->data = data;
this->priority = priority;
this->next = NULL;
}
};
class PriorityQueue {
Node* head;
public:
PriorityQueue()
{
head = new Node("Head", INT_MIN);
}
void pop()
{
// List is empty.
if(head->next == NULL)
return;
// Storing the first node in a temporary variable.
Node* temp = head->next;
// Shifting Next pointer of head node.
head->next = head->next->next;
// Free the first node.
free(temp);
}
void push(string tskNumber, int priority)
{
Node* newnode = new Node(tskNumber, priority);
Node* temp = head;
if(isEmpty())
{
head->next = newnode;
}
else
{
while(temp->next && temp->next->priority<=priority)
{
temp = temp->next;
}
newnode->next = temp->next;
temp->next = newnode;
}
}
void print()
{
Node* temp = head;
while( temp->next )
{
temp = temp->next;
cout << temp->data << " Priority:" << temp->priority <<endl;
}
}
void peek()
{
// Priority Queue is empty.
if(isEmpty())
{
cout<<"Nothing left to peek!\n";
}
else
{
cout << head->next->data << endl;
}
}
bool isEmpty()
{
// 'head' is pointing to a NULL pointer.
if(!head->next)
return true;
else
return false;
}
};
int main()
{
// Dynamic Binding to the PriorityQueue class.
PriorityQueue* tasks = new PriorityQueue();
int numTasks;
cout << "Number of tasks?\n";
cin >> numTasks;
for(int i=0; i < numTasks; i++)
{
string tskName;
int priority;
cin >> tskName >> priority;
tasks->push( tskName, priority );
}
// Let's see the new order of tasks with their priorities.
cout << "\nOrder of tasks and their respective priority:\n";
tasks->print();
// Let's pop elements one by one and check the front of our Priority Queue.
cout<<"Time to Pop:\n";
do
{
cout << "Task at top: ";
tasks->peek();
tasks->pop();
} while( !tasks->isEmpty() );
}

You can also try this code with Online C++ Compiler
Run Code
Input
Number of tasks?
3
Task1 3
Task2 1
Task3 2
Output
Order of tasks and their respective priorities:
Task2 Priority:1
Task3 Priority:2
Task1 Priority:3
Time to Pop:
Task at top: Task2
Task at top: Task3
Task at top: Task1
Read about Application of Queue in Data Structure here.
Frequently Asked Questions
Which data structure does a priority queue utilize?
The priority queue makes use of a heap data structure. Depending upon the requirements, it can be either a min-heap or a max-heap.
What is the insertion complexity for an element in the priority queue using a heap?
The insertion complexity for an element in the priority queue is O(logN) where N is the size of the priority queue.
What is the insertion complexity for an element in the priority queue using a Linked List?
The insertion complexity for an element in the priority queue is O(N) where N is the size of the priority queue.
Conclusion
We understand that you worked really hard in learning about the priority queue implementation and its application to help our friend Raj. We appreciate your efforts.
Recommended Readings:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
A good coder always practices what he/she learns. So head over to our practice platform Coding Ninjas Studio to practice top problems and many more. Coding Ninjas Studio also offers interesting interview experiences and blogs like this. So keep learning and Happy Coding!