Data Structure and Algorithm
Introduction to Priority Queue Data Structure with Practical Examples
 Priority Queue
 Heap
 Priority Queue Implementation Using Max Heap in C
 Priority Queue in C++ STL
 Applications of Priority Queue
 Run C Programming Online Compiler
Often, there is a need to store and access data while considering their assigned priorities. However, traditional data structures may require costly rearrangements when new elements are added or deleted, impacting performance. Priority Queues
offer a solution by efficiently arranging data according to their individual priorities, allowing access with low complexity.
¶Priority Queue
In a priority queue, each element comes with a priority
value when it’s added. We can only access one element at a time, and it’s always the one with the highest priority. The queue arranges elements so that those with higher priorities are at the front, and lowerpriority ones are at the back.With rebalancing it ensures that elements are stored in a manner that maintains this order, allowing for efficient retrieval based on priority.
Priority queues can be implemented using arrays, linked lists, heaps, or binary search trees. Each method has its pros and cons, suited for different needs and performance considerations. Based on how the priority queue arranges its elements with respect to priority, it can be classified into two types:
¶Min Priority Queue
In a min priority queue, elements with lower priority values are given higher priority. Therefore, the element with the minimum priority value is always at the front of the queue. This type of priority queue is often used when you need to retrieve the element with the lowest priority first.
¶Max Priority Queue
In a max priority queue, elements with higher priority values are given higher priority. Consequently, the element with the maximum priority value is placed at the front of the queue. Max priority queues are useful when you need to access the element with the highest priority first.
¶Heap
A heap is a complete binary tree, meaning except possibly for the last level all levels of the tree are fully filled, which is filled from left to right. Heaps find extensive applications in algorithms such as sorting, graph algorithms, and priority queue implementations due to their efficient operations. Depending on whether it is a max heap or min heap, each node must satisfy the heap property
.
¶Max Heap
In a max heap, the value of every parent node must be greater than or equal to the value of both its children. This means the largest value always sits at the root, making it easy to retrieve the “maximum” element efficiently.
¶Min Heap
Conversely, in a min heap, the value of every parent node must be less than or equal to the value of both its children. This ensures the smallest value resides at the root, facilitating the retrieval of the “minimum” element quickly.
¶Priority Queue Implementation Using Max Heap in C
#include <stdio.h>
#define MAX_SIZE 100
// Function to swap two elements in the array
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to heapify a subtree rooted at index 'rootIndex' in max heap
void maxHeapify(int arr[], int size, int rootIndex) {
int largest = rootIndex; // Initialize largest as root
int leftChild = 2 * rootIndex; // left = 2*i
int rightChild = 2 * rootIndex + 1; // right = 2*i + 1
// If left child is larger than root
if (leftChild <= size && arr[leftChild] > arr[largest])
largest = leftChild;
// If right child is larger than largest so far
if (rightChild <= size && arr[rightChild] > arr[largest])
largest = rightChild;
// If largest is not root
if (largest != rootIndex) {
swap(&arr[rootIndex], &arr[largest]);
// Recursively heapify the affected subtree
maxHeapify(arr, size, largest);
}
}
// Function to insertNode an element into the priority queue
void insertNode(int arr[], int *size, int value) {
if (*size == MAX_SIZE) {
printf("Queue is full. Cannot insertNode element.\n");
return;
}
// InsertNode the new element at the end of the heap
*size += 1;
arr[*size] = value;
// Heapify the tree from bottom to top
int currentIndex = *size;
while (currentIndex > 1 && arr[currentIndex / 2] < arr[currentIndex]) {
swap(&arr[currentIndex], &arr[currentIndex / 2]);
currentIndex = currentIndex / 2;
}
}
// Function to extract the maximum element from the priority queue
int extractMax(int arr[], int *size) {
if (*size <= 0) {
printf("Queue is empty. Cannot extract element.\n");
return 1;
}
// Store the root value which is the maximum element
int maxElement = arr[1];
// Replace the root with the last element
arr[1] = arr[*size];
*size = 1;
// Heapify the new root
maxHeapify(arr, *size, 1);
return maxElement;
}
// Function to delete an element at a given index from the priority queue
void deleteNode(int arr[], int *size, int index) {
if (index <= 0  index > *size) {
printf("Invalid index. Cannot delete element.\n");
return;
}
// Replace the element at the given index with the last element
arr[index] = arr[*size];
*size = 1;
// Heapify the tree from bottom to top
while (index > 1 && arr[index / 2] < arr[index]) {
swap(&arr[index], &arr[index / 2]);
index = index / 2;
}
// Heapify the subtree rooted at the index
maxHeapify(arr, *size, index);
}
int main() {
int priorityQueue[MAX_SIZE] = {0};
int size = 0;
// InsertNode elements into the priority queue
insertNode(priorityQueue, &size, 55);
insertNode(priorityQueue, &size, 35);
insertNode(priorityQueue, &size, 65);
insertNode(priorityQueue, &size, 90);
insertNode(priorityQueue, &size, 50);
insertNode(priorityQueue, &size, 65);
// Extract and print the maximum element
printf("Maximum element in the priority queue: %d\n", extractMax(priorityQueue, &size));
// Delete an element at index 2
deleteNode(priorityQueue, &size, 2);
// Extract and print the maximum element after deletion
printf("Maximum element in the priority queue after deletion: %d\n", extractMax(priorityQueue, &size));
insertNode(priorityQueue, &size, 80);
// Extract and print the maximum element after deletion
printf("Maximum element in the priority queue: %d\n", extractMax(priorityQueue, &size));
// Delete an element at index 2
deleteNode(priorityQueue, &size, 2);
// Extract and print the maximum element after deletion
printf("Maximum element in the priority queue after deletion: %d\n", extractMax(priorityQueue, &size));
return 0;
}
Maximum element in the priority queue: 90
Maximum element in the priority queue after deletion: 65
Maximum element in the priority queue: 80
Maximum element in the priority queue after deletion: 65
¶maxHeapify()
The maxHeapify
function is responsible for maintaining the heap property in a max heap, specifically at a given root index. It ensures that the subtree rooted at the specified index follows the max heap property, where each node is greater than or equal to its children. It identifies the largest element among the root and its children. If the largest element is not the root itself, it swaps the root with the largest child.This ensures that the largest element is moved up to the root position, maintaining the max heap property locally.
The time complexity of maxHeapify is O(log n)
, where n is the number of elements in the subtree rooted at the specified index. This is because the function descends down the tree height, which is logarithmic with respect to the number of elements in the subtree.
¶insertNode()
The insertNode
function adds a new element to the max heap, ensuring that the heap property is maintained. It inserts the element at the end of the heap and then adjusts the heap upwards if needed. This ensures that each parent node is greater than or equal to its children. It adjusts the heap upwards by comparing the new element with its parent and swapping if necessary. This process repeats recursively until the heap property is satisfied.
The time complexity of insertNode is O(log n)
, where n is the number of elements in the heap. This is due to the upward heapification process, which involves traversing the height of the heap. Since the height of a binary heap is logarithmic, insertion takes logarithmic time.
¶deleteNode()
The deleteNode
function removes an element from the max heap while maintaining the heap property. It replaces the element to be deleted with the last element in the heap and adjusts the heap structure upwards, if necessary, to ensure that the max heap property is preserved.
The time complexity of deleteNode() is O(log n)
, where n is the number of elements in the heap. Since the height of a binary heap is logarithmic, deletion takes logarithmic time.
¶Priority Queue in C++ STL
In C++, the Standard Template Library provides a priority queue implementation as part of the <queue>
header. The priority queue STL uses a maxheap
by default, meaning that the maximum element is always at the top. To use priority queue as minheap, we can use,
std::priority_queue<int, std::vector<int>, std::greater<int>>
¶Functions in C++ STL Priority Queue
#include <iostream>
#include <queue>
int main() {
// Creating a priority queue of integers
std::priority_queue<int> pq;
// Inserting elements into the priority queue
pq.push(10);
pq.push(30);
pq.push(20);
// Accessing the top (maximum) element of the priority queue
std::cout << "Top element: " << pq.top() << std::endl;
// Removing the top element from the priority queue
pq.pop();
// Accessing the top element after removal
std::cout << "Top element after pop: " << pq.top() << std::endl;
// Checking if the priority queue is empty
std::cout << "Priority queue is empty: " << (pq.empty() ? "true" : "false") << std::endl;
// Getting the size of the priority queue
std::cout << "Size of priority queue: " << pq.size() << std::endl;
return 0;
}
Top element: 30
Top element after pop: 20
Priority queue is empty: false
Size of priority queue: 2

push()
Inserts an element into the priority queue. Time ComplexityO(log n)
, where n is the number of elements in the priority queue. 
top()
Returns the current maximum (top) element in the priority queue. Time ComplexityO(1)
. 
pop()
Removes the current maximum (top) element from the priority queue. Time ComplexityO(log n)
, where n is the number of elements in the priority queue. 
empty()
Checks if the priority queue is empty. Time ComplexityO(1)
. 
size()
Returns the current number of elements in the priority queue. Time ComplexityO(1)
.
¶Applications of Priority Queue
Priority queues have various applications in computer science and realworld scenarios due to their ability to efficiently manage elements based on their priority.

Job Scheduling: Priority queues are used in job scheduling algorithms, where tasks or jobs are assigned priorities based on their urgency or importance. Jobs with higher priority are executed before those with lower priority.

Dijkstra’s Shortest Path Algorithm: Priority queues are used in Dijkstra’s algorithm to find the shortest paths between nodes in a graph. Nodes are processed based on their distance from the source node, with shorter paths given higher priority.

Huffman Coding: Priority queues are utilized in Huffman coding, a data compression algorithm. The algorithm constructs a binary tree of characters based on their frequencies, with characters having lower frequencies assigned higher priority in the priority queue.

Eventdriven Simulation: Priority queues are employed in eventdriven simulation systems to manage events based on their occurrence time. Events are scheduled and processed in chronological order, with events occurring earlier given higher priority.

Operating System Tasks: Priority queues are used in operating systems to manage tasks and processes based on their priority levels. Higherpriority processes are executed before lowerpriority ones, allowing the system to respond promptly to critical tasks.

Network Routing: Priority queues are utilized in network routing protocols to prioritize packets based on their importance or type of service. Packets with higher priority are forwarded with minimal delay, ensuring timely delivery of critical data.
¶Run C Programming Online Compiler
To make your learning more effective, exercise the coding examples in the text editor below.
Introduction to Map Data Structure with Practical Examples
Introduction to Trie Data Structure with Practical Examples
All Tutorials in this playlist
Popular Tutorials
Categories

Artificial Intelligence (AI)
2

Bash Scripting
1

Bootstrap CSS
0

C Programming
14

C#
0

ChatGPT
1

Code Editor
2

Computer Engineering
3

CSS
28

Data Structure and Algorithm
9

Design Pattern in PHP
2

Design Patterns  Clean Code
1

EBook
1

Git Commands
1

HTML
19

Interview Prepration
2

Java Programming
0

JavaScript
12

Laravel PHP Framework
37

Mysql
1

Node JS
1

Online Business
0

PHP
28

Programming
8

Python
12

React Js
19

React Native
1

Redux
2

Rust Programming
15

Tailwind CSS
1

Typescript
10

Uncategorized
0

Vue JS
1

Windows Operating system
1

Woocommerce
1

WordPress Development
2
Tags
 Artificial Intelligence (AI)
 Bash Scripting
 Business
 C
 C Programming
 Csharp programming
 C++
 Code Editor
 Computer Engineering
 CSS
 Data Structure and Algorithm
 Database
 Design pattern
 Express JS
 git
 Git Commands
 github
 HTML
 Java
 JavaScript
 Laravel
 Mathematics
 MongoDB
 Mysql
 Node JS
 PHP
 Programming
 Python
 React Js
 Redux
 Rust Programming Language
 TypeScript
 Vue JS
 Windows terminal
 Woocommerce
 WordPress
 WordPress Plugin Development