Priority Queue implementation in C
An entry in a priority queue is arranged according to its priority value. Generally speaking, elements with higher priority values are retrieved ahead of elements with lower priority.
Every entry in a priority queue has a priority value assigned to it. An element is added to the queue and is placed according to its priority value. An element with a high priority value, for instance, might be added to a priority queue in the front, while an element with a low priority value might be added near the back.
A priority queue can be implemented in various ways, such as an array, binary search tree, linked list, or heap. Each approach has benefits and drawbacks, and the optimal one will depend on your application's particular requirements.
In real-time systems, where the order in which elements are processed might have important ramifications, priority queues are frequently utilized. In order to increase their efficiency, they are also employed in algorithms like the A* search algorithm for pathfinding and Dijkstra's algorithm for locating the shortest route in a graph.
Qualities of a Priority Queue
Thus, an extension of the queue with the following characteristics is called a priority queue.
- Every item has a corresponding priority.
- High-priority elements are dequeued ahead of low-priority elements.
- When two elements share the same priority, they are handled in the queue order that they appear in.
How are the entries in a priority queue given priority?
The value of an element is typically taken into account when allocating a priority in a priority queue.
For instance, the highest-value element receives the most priority, whereas the lowest-value element receives the lowest priority. It is also possible to employ the opposite scenario, where the element with the lowest value is given the most precedence. Additionally, we can assign priorities based on our needs.
Functions of a Priority Queue:
A priority queue often supports the following functions:
1) Entry into a Priority Queue
A new element enters a priority queue and advances from top to bottom and left to right to occupy the vacant slot.
If an element is not at the proper location, it will be compared to the parent node, though. If it is not in the proper order, the elements are switched. The switching operation is repeated until each element is positioned correctly.
2) Deletion in a Priority List
As you are aware, the root node is the maximum element in a max heap. Additionally, the element with the highest priority will be eliminated first. Consequently, the root node is eliminated from the queue. This removal creates a void, and new insertions will fill it up. In order to keep the heap invariant, it then compares the just inserted element with every element in the queue.
3) Peek in a Priority Queue
Without removing the node from the priority queue, this action assists in returning the maximum element from the Max Heap or the minimum element from the Min Heap.
Priority queue types include:
1) Ascending Order Priority Queue
As the name implies, the element in the priority list with the lower priority value is given a greater priority in an ascending-order priority queue. As an illustration, suppose we have the following components in ascending order in a priority queue: 4, 6, 8, 9, 10. In this case, 4 is the lowest number so that it will be given the highest priority in a priority queue. As a result, when we dequeue from this kind of priority queue, 4 is removed from the queue and returned.
2) A Priority Queue in decreasing order
As you may know, the root node is the maximum element in a max heap. Additionally, the element with the highest priority will be eliminated first. The root node is consequently taken out of the queue. This deletion creates a void that will eventually be filled with new insertions. The newly inserted element is then compared to every other entry in the queue in order to maintain the heap invariant.
What distinguishes a normal queue from a priority queue?
Elements in a queue follow the first-in-first-out (FIFO) rule without any priority, whereas elements in a priority queue have a priority. The elements with the highest priority are the first to be served.
Use an Array to Implement a Priority Queue:
The following structure can be used as an array for straightforward implementation.
struct item
{
int item;
int priority;
}
- The enqueue() function is employed to append fresh data to the queue.
- The element in the queue with the highest priority is removed using the dequeue() function.
- The function peek()/top() retrieves the element with the highest priority from the queue without eliminating it.
Program
#include <stdio.h>
#include <limits.h>
//Structure for the elements in the
// priority queue
struct item {
int value;
int priority;
};
// Store the element of a priority queue
struct item pr[100000];
// Pointer to the last index
int size = -1;
// Function to insert a new element
// into the priority queue
void enqueue(int value, int priority)
{
// Increase the size
size++;
// Insert the element
pr[size].value = value;
pr[size].priority = priority;
}
// Function to check the top element
int peek()
{
int highestPriority = INT_MIN;
int ind = -1;
// Check for the element with
// highest priority
for (int i = 0; i <= size; i++) {
// If the priority is the same, choose
//The element with the
// highest value
if (highestPriority == pr[i].priority && ind > -1
&& pr[ind].value < pr[i].value) {
highestPriority = pr[i].priority;
ind = i;
}
else if (highestPriority < pr[i].priority) {
highestPriority = pr[i].priority;
ind = i;
}
}
// Return the position of the element
return ind;
}
// Function to remove the element with
// the highest priority
void dequeue()
{
// Find the position of the element
// with highest priority
int ind = peek();
// Shift the element one index before
// from the position of the element
// with the highest priority is found
for (int i = ind; i < size; i++) {
pr[i] = pr[i + 1];
}
// Decrease the size of the
// priority queue by one
size--;
}
// Driver Code
int main()
{
// Function Call to insert elements
// as per the priority
enqueue(10, 2);
enqueue(14, 4);
enqueue(16, 4);
enqueue(12, 3);
// Stores the top element
// at the moment
int ind = peek();
printf("%d\n", pr[ind].value);
// Dequeue the top element
dequeue();
// Check the top element
ind = peek();
printf("%d\n", pr[ind].value);
// Dequeue the top element
dequeue();
// Check the top element
ind = peek();
printf("%d\n", pr[ind].value);
return 0;
}
Output
![Priority Queue implementation in C](https://static.tutorialandexample.com/c/priority-queue-implementation-in-c1.png)
Priority Queue Applications:
- CPU Scheduling
- Graph algorithms such as Prim's Minimum Spanning Tree, Dijkstra's Shortest Path Algorithm, etc.
- Stack Configuration
- Every application in the queue involves a priority.
- Compression of data in Huffman code
- Event-driven simulation, such as a queue of consumers waiting.
- Determining the Kth element's size, if any.
Benefits of Priority Queue:
- It facilitates quicker access to the elements. The highest priority element can be quickly retrieved without having to look through the full queue since elements in a priority queue are arranged according to priority.
- A priority queue's elements are arranged dynamically. When priorities change, the priority queue can dynamically rearrange itself by allowing elements to have their priority values modified.
- Implementing effective algorithms is possible. Many algorithms, such as the A* search algorithm for pathfinding and Dijkstra's algorithm for determining the shortest route in a network, use priority queues to increase their efficiency.
- Priority queues are a component of real-time systems. They are frequently employed when speed is of the essence, enabling rapid access to the element with the highest priority.
Cons of Using a Priority Queue:
It is less predictable at times. This is because, unlike other data structures like stacks or queues, which have a first-in, first-out (FIFO) or last-in, first-out (LIFO) order, the components in a priority queue are arranged according to their priority values, making the order in which they are retrieved potentially less predictable.
Priority queues are more complicated than straightforward data structures like arrays and linked lists and may be more challenging to set up and manage.
Storing the priority value for every entry in a priority queue can require more memory, which could be problematic for systems with constrained resources.
It's not necessarily the most efficient data format. Certain tasks, including determining the minimum or maximum entry in the queue, may occasionally be more effectively performed using alternative data structures, such as heaps or binary search trees.