Last Updated on May 23, 2023 by Prepbytes
Priority queues are fundamental data structures that play a crucial role in various computer science applications, from operating systems to graph algorithms and event-driven simulations. They provide efficient access to the highest-priority element, allowing us to process tasks in order of importance. While there are several ways to implement priority queues, one of the most straightforward and commonly used approaches is by utilizing arrays in the C programming language.
In this article, we will delve into the world of priority queues and explore their implementation using arrays in C. We will start by understanding the basic concepts of priority queues and their importance in solving real-world problems efficiently. Then, we will walk through the step-by-step process of creating a priority queue using arrays, discussing the essential operations involved, such as insertion, deletion, and retrieval of the highest-priority element.
Priority Queue
Each element in a priority queue is an abstract data structure with a priority value. For instance, on any airline, "First-Class" or "Business" baggage always arrives first.
A priority Queue is a kind of queue that has the following characteristics:
- Priority order determines which items are taken out of the queue first.
- If two items in the priority queue have the same priority, the components will be handled in the order that they appear in the queue.
The priority queue is frequently utilised in a variety of applications, including managing shared resources among several processes, task scheduling algorithms, CPU and disc scheduling, etc.
How is the Priority Value assigned in the Priority Queue?
Priority value is provided when an element is inserted in C. Additionally, items will be chosen for carrying out the actions based on the priority value. The actions will prioritize components with higher priority values over those with lower priority values.
The main difference between a queue and a priority queue:
The element that was added first to the queue will be the first to be removed. However, in a priority queue, the element with the highest priority will be the first to be dequeued.
The outcome of an element being removed from the priority queue will be in sorted order, which may be growing or decreasing. When in a queue, elements are released in FIFO (First in First out) order.
Code Implementation of Priority Queue using Array in C
#include<stdio.h>
#include<limits.h>
#define MAX 100
int idx = -1;
int pqVal[MAX];
int pqPriority[MAX];
int isEmpty(){
return idx == -1;
}
int isFull(){
return idx == MAX - 1;
}
void enqueue(int data, int priority)
{
if(!isFull()){
idx++;
pqVal[idx] = data;
pqPriority[idx] = priority;
}
}
int peek()
{
int maxPriority = INT_MIN;
int indexPos = -1;
for (int i = 0; i <= idx; i++) {
if (maxPriority == pqPriority[i] && indexPos > -1 && pqVal[indexPos] < pqVal[i])
{
maxPriority = pqPriority[i];
indexPos = i;
}
else if (maxPriority < pqPriority[i]) {
maxPriority = pqPriority[i];
indexPos = i;
}
}
return indexPos;
}
void dequeue()
{
if(!isEmpty())
{
int indexPos = peek();
for (int i = indexPos; i < idx; i++) {
pqVal[i] = pqVal[i + 1];
pqPriority[i] = pqPriority[i + 1];
}
idx--;
}
}
void display(){
for (int i = 0; i <= idx; i++) {
printf("(%d, %d)\n",pqVal[i], pqPriority[i]);
}
}
int main()
{
enqueue(5, 1);
enqueue(10, 3);
enqueue(15, 4);
enqueue(20, 5);
enqueue(25, 2);
printf("Priority Queue Before Dequeue : \n");
display();
dequeue();
dequeue();
printf("\nPriority Queue After Dequeue : \n");
display();
return 0;
}
Conclusion
In conclusion, we have explored the implementation of priority queue using array in C programming language. Throughout this article, we have discussed the importance of priority queues as efficient data structures for handling tasks with varying priorities. By utilizing arrays, we have created a simple yet effective implementation of a priority queue that allows for efficient insertion, deletion, and retrieval of the highest-priority element.
Implementing a priority queue using arrays in C provides several advantages. First and foremost, it offers a straightforward approach that is easy to understand, making it an excellent choice for beginners to learn about data structures and algorithms. The simplicity of the array-based implementation allows programmers to focus on the core concepts of priority queues without getting overwhelmed by complex data structures.
FAQ
Q1: Why would I use an array-based implementation for a priority queue in C?
Ans. Array-based implementations offer simplicity and ease of understanding. They provide constant-time access to elements, making retrieval of the highest-priority element efficient. Array-based priority queues are particularly useful when the number of elements is known in advance or when a fixed-size priority queue is required.
Q2: How does the insertion operation work in an array-based priority queue?
Ans. To insert an element into an array-based priority queue, you compare the priority of the new element with existing elements in the array, finding the appropriate position to maintain the priority order. The new element is inserted at that position, shifting other elements as necessary.
Q3: How does the deletion operation work in an array-based priority queue?
Ans. In an array-based priority queue, the deletion operation typically involves removing the highest-priority element from the front of the array. Once the element is removed, the remaining elements are shifted to fill the gap, preserving the order of priorities.
Q4: How do I retrieve the highest-priority element from an array-based priority queue?
Ans. The highest-priority element in an array-based priority queue is always located at the front of the array. You can simply access the first element of the array to retrieve it.
Q5: Can the size of an array-based priority queue be dynamically adjusted?
Ans. No, the size of an array-based priority queue is typically fixed at the time of creation. If the number of elements exceeds the predefined array size, additional considerations, such as resizing the array or implementing a dynamic array, may be required.
Q6: What are the time and space complexities of array-based priority queues?
Ans. The time complexity of insertion and deletion operations in an array-based priority queue is typically O(n), where n is the number of elements in the queue. Retrieving the highest-priority element is a constant-time operation (O(1)). The space complexity is O(n) as well, as it depends on the number of elements stored in the array.