Priority Queue in Data Structure: Characteristics, Types & Implementation
Updated on Mar 07, 2025 | 14 min read | 59.6k views
Share:
For working professionals
For fresh graduates
More
Updated on Mar 07, 2025 | 14 min read | 59.6k views
Share:
Table of Contents
How do Google Maps find the fastest route to your destination? It uses a priority queue in data structure to make this possible. A great priority queue example is Dijkstra’s Shortest Path algorithm uses a min priority queue to rank all possible paths based on their distance. The path with the highest priority, often the shortest, is chosen as the best route.
A priority queue is a special data structure that processes elements based on their priority instead of the order they are added. This makes it different from a regular queue and incredibly useful in applications like navigation, task scheduling, and more.
In this blog, we’ll explore:
Let’s understand why priority queues are so important in solving real-world problems!
Check out: Free Python Course with Certification
A priority queue in data structure is an abstract data type (ADT) that organizes elements based on their priority rather than the order in which they were added. Unlike a regular queue, which follows a first-in-first-out (FIFO) order, a priority queue processes the element with the highest priority first. This makes it a versatile tool for handling scenarios where priority matters more than sequence.
Let’s consider a priority queue example in data structure using a min-priority queue, where elements are arranged in ascending order:
Unlike a standard queue, where elements are processed in the order they arrive, a priority queue in data structure ensures that high-priority items are handled first. Here are its core characteristics:
In a hospital’s emergency room, a patient with a critical condition would be treated first (highest priority). If two patients have similar conditions, the one who arrived is attended to first.
Priority queues are essential in scenarios requiring efficient and organized task processing, ensuring that the most critical items are addressed without delays.
A priority queue organizes elements based on their assigned priority, and the type of priority queue determines how these priorities are interpreted. There are two primary types of priority queues: ascending order priority queues and descending order priority queues. These structures differ in how they assign priority and process elements. Let’s explore them in detail.
In an ascending order priority queue in data structure, elements with lower values are considered higher priority. This means that when dequeuing, the smallest value is removed first. The priority is inversely proportional to the numerical value of the elements.
Consider a priority queue with elements: 2, 4, 6, 8, 10.
In a descending order priority queue, elements with higher values are given precedence. This means that the largest value is dequeued first. The priority is directly proportional to the numerical value of the elements.
Consider a priority queue example with elements: 1, 2, 3, 4, 5, 9.
Feature |
Ascending Order Priority Queue |
Descending Order Priority Queue |
Priority Rule |
Lower value = Higher priority |
Higher value = Higher priority |
First Element Dequeued |
Smallest value |
Largest value |
Common Implementation |
Min-heap |
Max-heap |
Primary Use Case |
Pathfinding, cost-efficient operations |
Task scheduling, urgent tasks management |
Priority queue in data structure can be implemented using various data structures. Each method offers distinct advantages and trade-offs, depending on the use case.
A linked list can implement a priority queue in data structure by maintaining elements in an order based on their priority. New elements are inserted at the correct position to preserve the order.
Implement a priority queue in data structure using a linked list where elements are inserted based on their priority, and the highest-priority element can be dequeued efficiently.
cpp
#include <bits/stdc++.h>
using namespace std;
// Node structure for the priority queue
struct Node {
int data;
int priority;
Node* next;
};
// Function to create a new node
Node* newNode(int d, int p) {
Node* temp = new Node();
temp->data = d;
temp->priority = p;
temp->next = nullptr;
return temp;
}
// Function to remove the element with the highest priority
void pop(Node** head) {
Node* temp = *head;
*head = (*head)->next;
delete temp;
}
// Function to add an element into the priority queue
void push(Node** head, int d, int p) {
Node* temp = newNode(d, p);
// If the queue is empty or new node has higher priority than the head
if (*head == nullptr || (*head)->priority < p) {
temp->next = *head;
*head = temp;
} else {
Node* start = *head;
while (start->next != nullptr && start->next->priority >= p) {
start = start->next;
}
temp->next = start->next;
start->next = temp;
}
}
// Function to get the element with the highest priority
int peek(Node* head) {
return head->data;
}
// Driver code
int main() {
Node* pq = nullptr;
push(&pq, 10, 2);
push(&pq, 20, 4);
push(&pq, 30, 3);
push(&pq, 40, 1);
while (pq != nullptr) {
cout << "Top element: " << peek(pq) << endl;
pop(&pq);
}
return 0;
}
A binary heap is the most efficient way to implement a priority queue in data structure. It uses a complete binary tree structure, ensuring logarithmic time for insertion and deletion operations.
Implement a priority queue in data structure using a binary heap, allowing efficient insertion and removal of the highest-priority element.
cpp
#include <bits/stdc++.h>
using namespace std;
// Class for a max-heap-based priority queue
class PriorityQueue {
vector<int> heap;
// Heapify-down to maintain the heap property after deletion
void heapifyDown(int idx) {
int largest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < heap.size() && heap[left] > heap[largest]) largest = left;
if (right < heap.size() && heap[right] > heap[largest]) largest = right;
if (largest != idx) {
swap(heap[idx], heap[largest]);
heapifyDown(largest);
}
}
// Heapify-up to maintain the heap property after insertion
void heapifyUp(int idx) {
if (idx == 0) return;
int parent = (idx - 1) / 2;
if (heap[idx] > heap[parent]) {
swap(heap[idx], heap[parent]);
heapifyUp(parent);
}
}
public:
// Insert a new element
void push(int val) {
heap.push_back(val);
heapifyUp(heap.size() - 1);
}
// Remove the element with the highest priority
void pop() {
if (heap.empty()) return;
heap[0] = heap.back();
heap.pop_back();
heapifyDown(0);
}
// Get the element with the highest priority
int peek() {
return heap.empty() ? -1 : heap[0];
}
// Check if the queue is empty
bool isEmpty() {
return heap.empty();
}
};
// Driver code
int main() {
PriorityQueue pq;
pq.push(10);
pq.push(50);
pq.push(30);
pq.push(20);
while (!pq.isEmpty()) {
cout << "Top element: " << pq.peek() << endl;
pq.pop();
}
return 0;
}
Priority queues in data structure can also be implemented using arrays, either ordered or unordered.
Implement a priority queue using an array, where elements are stored with their priority values, and the highest-priority element is retrieved efficiently.
cpp
#include <bits/stdc++.h>
using namespace std;
// Priority queue using unordered array
class PriorityQueue {
vector<pair<int, int>> arr;
public:
// Add an element with priority
void push(int val, int priority) {
arr.push_back({priority, val});
}
// Remove the element with the highest priority
void pop() {
auto it = max_element(arr.begin(), arr.end());
arr.erase(it);
}
// Get the element with the highest priority
int peek() {
auto it = max_element(arr.begin(), arr.end());
return it->second;
}
// Check if the queue is empty
bool isEmpty() {
return arr.empty();
}
};
// Driver code
int main() {
PriorityQueue pq;
pq.push(10, 2);
pq.push(20, 5);
pq.push(15, 3);
while (!pq.isEmpty()) {
cout << "Top element: " << pq.peek() << endl;
pq.pop();
}
return 0;
}
A binary search tree (e.g., AVL or Red-Black Tree) can implement a priority queue in data structure by maintaining priority ordering in its structure.
Operation |
Unordered Array |
Ordered Array |
Binary Heap |
BST |
Insert |
O(1) |
O(n) |
O(logn) |
O(logn) |
Peek |
O(n) |
O(1) |
O(1) |
O(1) |
Delete |
O(n) |
O(1) |
O(logn) |
O(logn) |
Priority queues in data structure are widely used in various systems and algorithms where prioritizing tasks or data is essential. Here are some common applications explained with practical priority queue examples to show their importance.
Operating systems use priority queues to manage and schedule tasks based on their priority level.
Priority Queue Example:
In a computer system, processes are given priority levels. For instance:
The CPU executes Task A first, followed by Task B and Task C. This ensures urgent tasks, such as system updates, are completed before less critical ones. Priority queues make this scheduling efficient and organized.
In this algorithm, a min-priority queue in data structure stores nodes based on their current shortest distance from the source. The node with the smallest distance is processed first.
Priority Queue Example:
In a navigation system, such as Google Maps, the shortest route is calculated using Dijkstra’s algorithm. A priority queue helps prioritize the next closest node to evaluate, ensuring the most efficient path is found.
This algorithm uses a min-priority queue to select edges with the smallest weights to construct a minimum spanning tree.
Priority Queue Example:
In a network design, such as laying fiber-optic cables, Prim’s algorithm helps minimize costs by selecting the shortest connections between points.
Priority queues are used in Huffman coding, a popular method for reducing file sizes.
How It Works:
Huffman coding assigns shorter binary codes to frequently occurring characters and longer codes to less frequent ones. A min-priority queue combines the characters with the lowest frequencies first.
Priority Queue Example:
If a text contains the following character frequencies:
The priority queue helps build a binary tree where characters with the smallest frequencies (C and D) are combined first. This tree generates efficient encodings, reducing the overall size of the compressed file.
Priority queues are used in simulations to handle events based on their priority, ensuring critical tasks are processed before others.
Priority Queue Example:
In a hospital’s emergency room, patients are assigned priorities based on the severity of their condition:
A priority queue ensures Patient X is attended to first, followed by Patient Z and Patient Y.
Other Simulation Scenarios:
Routers use priority queues to manage data packets. Critical packets, like live video streams or emergency signals, are prioritized over less important packets like file downloads.
Priority Queue Example:
If a router processes the following packets:
The priority queue ensures live stream data is transmitted first, maintaining smooth performance for time-sensitive tasks.
Priority queues are used in A* search to explore paths based on their cost and estimated distance to the target.
Priority Queue Example:
In robotic navigation, the algorithm uses a priority queue to evaluate the most promising paths first, reducing time and computation required to reach the destination.
Priority queues are a game-changer in data structures, powering solutions in navigation, scheduling, and more. Learning them sharpens your problem-solving skills and helps you tackle advanced algorithms like Dijkstra’s shortest path and Huffman coding.
Ready to strengthen your skills? upGrad’s expert-led courses in data structures and algorithms are the perfect way to grow.
Your next career move starts here! Explore upGrad Courses Now!
Elevate your expertise with our range of Popular Data Science Courses. Browse the programs below to discover your ideal fit.
Advance your in-demand data science skills with our top programs. Discover the right course for you below.
Explore popular articles related to data science to enhance your knowledge. Browse the programs below to find your ideal match.
Get Free Consultation
By submitting, I accept the T&C and
Privacy Policy
Start Your Career in Data Science Today
Top Resources