Priority Queue in C
A data structure called a priority queue holds items with assigned priorities. It enables quick element insertion and retrieval of items based on priority.
There are several ways to create a priority queue in C. Using a binary heap is one such implementation.
How do priority queues and regular queues vary from one another?
The primary distinction between a priority and a regular queue is the sequence in which entries are retrieved or dequeued.
- According to the First-In-First-Out (FIFO) concept, components usually are enqueued in the rear and dequeued from the front. The first item to be dequeued is the one that has been in the queue the longest.
- Each element is given a priority in a priority queue, and the one with the greatest priority is the first to be removed from the queue. The sequence of dequeuing is independent of the order of insertion. Regardless of the arrival sequence, items with higher priority take precedence over those with lower priorities.
Procedures in the priority queue in C
The frequent operations carried out on a priority queue in C consist of the following:
createPriorityQueue
This procedure creates an empty priority queue.
PriorityQueue* createPriorityQueue();
enqueue:
The element added by this action is added to the priority queue along with its priority.
void enqueue (PriorityQueue* queue, int priority, ElementType element);
dequeue:
The highest-priority element is removed from the priority queue and returned in this action.
ElementType dequeue (PriorityQueue* queue);
peek:
Without deleting it, this procedure retrieves the element from the priority queue with the greatest priority.
ElementType peek (PriorityQueue* queue);
is Empty:
When the priority queue is empty, this procedure verifies it.
int isEmpty(PriorityQueue* queue);
Different priority queue types in C
- Priority Queue Based on Arrays:
- With this method, the components of the priority queue may be stored in a dynamic array. The components are arranged according to priority.
- The insertion may be accomplished by determining the new element's proper place based on its priority and moving existing components correspondingly.
- By deleting the element with the most significant priority (often the first element) and relocating the other components, deletion can be accomplished.
- If the queue is enormous and requires frequent adjustments, the major disadvantage of this solution is that the insertion and deletion procedures may need to be more efficient.
Program:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
int priority;
struct Node* next;
} Node;
typedef struct PriorityQueue {
Node* head;
} PriorityQueue;
Node* createNode(int data, int priority) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->priority = priority;
newNode->next = NULL;
return newNode;
}
PriorityQueue* createPriorityQueue() {
PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
pq->head = NULL;
return pq;
}
int isEmpty(PriorityQueue* pq) {
return (pq->head == NULL);
}
void enqueue(PriorityQueue* pq, int data, int priority) {
Node* newNode = createNode(data, priority);
if (isEmpty(pq) || priority < pq->head->priority) {
newNode->next = pq->head;
pq->head = newNode;
} else {
Node* current = pq->head;
while (current->next != NULL && current->next->priority <= priority) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
int dequeue(PriorityQueue* pq) {
if (isEmpty(pq)) {
printf("Priority queue is empty.\n");
return -1;
}
Node* temp = pq->head;
int data = temp->data;
pq->head = pq->head->next;
free(temp);
return data;
}
void display(PriorityQueue* pq) {
if (isEmpty(pq)) {
printf("Priority queue is empty.\n");
return;
}
Node* current = pq->head;
while (current != NULL) {
printf("(%d, %d) ", current->data, current->priority);
current = current->next;
}
printf("\n");
}
int main() {
PriorityQueue* pq = createPriorityQueue();
enqueue(pq, 5, 2);
enqueue(pq, 10, 1);
enqueue(pq, 3, 3);
printf("Priority queue: ");
display(pq);
printf("Dequeued element: %d\n", dequeue(pq));
printf("Priority queue after dequeue: ");
display(pq);
return 0;
}
Output:
- Binarized Priority Queue:
- When a binary tree fully meets the heap property, it is called a binary heap—a maximum heap of parent nodes over child nodes.
- These operations may be completed in O (log n) time complexity, where n is the number of items, making this implementation efficient for insertion and deletion operations.
- With an array, each element's parent and child nodes are determined by their location, simulating a binary heap.
- An array of items must be constructed into a binary heap in O(n) time.
Program:
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int data;
int priority;
} Element;
typedef struct {
Element* elements;
int capacity;
int size;
} PriorityQueue;
PriorityQueue* createPriorityQueue(int capacity) {
PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
pq->elements = (Element*)malloc(sizeof(Element) * (capacity + 1));
pq->capacity = capacity;
pq->size = 0;
return pq;
}
void swap(Element* a, Element* b) {
Element temp = *a;
*a = *b;
*b = temp;
}
void enqueue(PriorityQueue* pq, int data, int priority) {
if (pq->size == pq->capacity) {
printf("Priority queue is full.\n");
return;
}
Element newElement;
newElement.data = data;
newElement.priority = priority;
int i = pq->size + 1;
pq->elements[i] = newElement;
pq->size++;
while (i > 1 && pq->elements[i].priority < pq->elements[i / 2].priority) {
swap(&pq->elements[i], &pq->elements[i / 2]);
i = i / 2;
}
}
int dequeue(PriorityQueue* pq) {
if (pq->size == 0) {
printf("Priority queue is empty.\n");
return -1;
}
int data = pq->elements[1].data;
pq->elements[1] = pq->elements[pq->size];
pq->size--;
int i = 1;
while (1) {
int smallest = i;
int leftChild = 2 * i;
int rightChild = 2 * i + 1;
if (leftChild <= pq->size && pq->elements[leftChild].priority < pq->elements[smallest].priority)
smallest = leftChild;
if (rightChild <= pq->size && pq->elements[rightChild].priority < pq->elements[smallest].priority)
smallest = rightChild;
if (smallest == i)
break;
swap(&pq->elements[i], &pq->elements[smallest]);
i = smallest;
}
return data;
}
int isEmpty(PriorityQueue* pq) {
return (pq->size == 0);
}
void display(PriorityQueue* pq) {
if (isEmpty(pq)) {
printf("Priority queue is empty.\n");
return;
}
for (int i = 1; i <= pq->size; i++) {
printf("(%d, %d) ", pq->elements[i].data, pq->elements[i].priority);
}
printf("\n");
}
int main() {
PriorityQueue* pq = createPriorityQueue(100);
enqueue(pq, 5, 2);
enqueue(pq, 10, 1);
enqueue(pq, 3, 3);
printf("Priority queue: ");
display(pq);
printf("Dequeued element: %d\n", dequeue(pq));
printf("Priority queue after dequeue: ");
display(pq);
return 0;
}
Output:
- Priority Queue for the Fibonacci Heap:
- The Fibonacci heap is an effective data structure for insertion, deletion, and decrease-key operations with amortized O (1) time complexity.
- Although this system is more challenging than the first two approaches, it offers improved time complexity for some tasks.
- For situations requiring a lot of decrease-key operations, Fibonacci heaps are appropriate.
- Fibonacci heap implementation might be more complex and require more sophisticated data structures and algorithms.
Program:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
typedef struct Node {
int data;
int priority;
struct Node* parent;
struct Node* child;
struct Node* left;
struct Node* right;
bool marked;
int degree;
} Node;
typedef struct FibonacciHeap {
Node* min;
int numNodes;
} FibonacciHeap;
FibonacciHeap* createFibonacciHeap() {
FibonacciHeap* fh = (FibonacciHeap*)malloc(sizeof(FibonacciHeap));
fh->min = NULL;
fh->numNodes = 0;
return fh;
}
Node* createNode(int data, int priority) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->priority = priority;
newNode->parent = NULL;
newNode->child = NULL;
newNode->left = newNode;
newNode->right = newNode;
newNode->marked = false;
newNode->degree = 0;
return newNode;
}
bool isEmpty(FibonacciHeap* fh) {
return (fh->min == NULL);
}
void insertNode(FibonacciHeap* fh, Node* node) {
if (isEmpty(fh)) {
fh->min = node;
} else {
node->left = fh->min;
node->right = fh->min->right;
fh->min->right->left = node;
fh->min->right = node;
if (node->priority < fh->min->priority) {
fh->min = node;
}
}
fh->numNodes++;
}
Node* extractMin(FibonacciHeap* fh) {
Node* minNode = fh->min;
if (minNode != NULL) {
if (minNode->child != NULL) {
Node* child = minNode->child;
Node* firstChild = child;
do {
Node* nextChild = child->right;
insertNode(fh, child);
child->parent = NULL;
child = nextChild;
} while (child != firstChild);
}
minNode->left->right = minNode->right;
minNode->right->left = minNode->left;
if (minNode == minNode->right) {
fh->min = NULL;
} else {
fh->min = minNode->right;
consolidate(fh);
}
fh->numNodes--;
}
return minNode;
}
void consolidate (FibonacciHeap* fh) {
int maxDegree = (int)(log(fh->numNodes) / log(2)) + 1;
Node* degreeTable[maxDegree];
for (int i = 0; i < maxDegree; i++) {
degreeTable[i] = NULL;
}
Node* current = fh->min;
Node* start = fh->min;
do {
Node* x = current;
int degree = x->degree;
while (degreeTable[degree] != NULL) {
Node* y = degreeTable[degree];
if (y->priority < x->priority) {
Node* temp = x;
x = y;
y = temp;
}
if (y == start) {
start = start->right;
}
if (y == current) {
current = current->right;
}
link(fh, y, x);
degreeTable[degree] = NULL;
degree++;
}
degreeTable[degree] = x;
current = current->right;
} while (current != start);
fh->min = start;
for (int i = 0; i < maxDegree; i++) {
if (degreeTable[i] != NULL && degreeTable[i]->priority < fh->min->priority) {
fh->min = degreeTable[i];
}
}
}
void link(FibonacciHeap* fh, Node* y, Node* x) {
y->left->right = y->right;
y->right->left = y->left;
if (x->child == NULL) {
x->child = y;
y->left = y;
y->right = y;
} else {
y->left = x->child;
y->right = x->child->right;
x->child->right->left = y;
x->child->right = y;
}
y->parent = x;
y->marked = false;
x->degree++;
}
void display(FibonacciHeap* fh) {
if (isEmpty(fh)) {
printf("Fibonacci heap is empty.\n");
return;
}
printf("Fibonacci heap: ");
Node* current = fh->min;
do {
printf("(%d, %d) ", current->data, current->priority);
current = current->right;
} while (current != fh->min);
printf("\n");
}
int main() {
FibonacciHeap* fh = createFibonacciHeap();
Node* node1 = createNode(5, 2);
insertNode(fh, node1);
Node* node2 = createNode(10, 1);
insertNode(fh, node2);
Node* node3 = createNode(3, 3);
insertNode(fh, node3);
printf("Fibonacci heap: ");
display(fh);
printf("Extracted minimum element: (%d, %d)\n", fh->min->data, fh->min->priority);
extractMin(fh);
printf("Fibonacci heap after extraction: ");
display(fh);
return 0;
}
Output:
- Linked list-based priority queue:
In C, a linked list data structure that representing each node as a priority queue element can be used to create a linked list-based priority queue. The element value and the priority value are both present in each node.
Program:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
int priority;
struct Node* next;
} Node;
typedef struct PriorityQueue {
Node* head;
} PriorityQueue;
Node* createNode(int data, int priority) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->priority = priority;
newNode->next = NULL;
return newNode;
}
PriorityQueue* createPriorityQueue() {
PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
pq->head = NULL;
return pq;
}
int isEmpty(PriorityQueue* pq) {
return (pq->head == NULL);
}
void enqueue(PriorityQueue* pq, int data, int priority) {
Node* newNode = createNode(data, priority);
if (isEmpty(pq) || priority < pq->head->priority) {
newNode->next = pq->head;
pq->head = newNode;
} else {
Node* current = pq->head;
while (current->next != NULL && current->next->priority <= priority) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
int dequeue(PriorityQueue* pq) {
if (isEmpty(pq)) {
printf("Priority queue is empty.\n");
return -1; // or any appropriate value to indicate an error
}
Node* temp = pq->head;
int data = temp->data;
pq->head = pq->head->next;
free(temp);
return data;
}
void display(PriorityQueue* pq) {
if (isEmpty(pq)) {
printf("Priority queue is empty.\n");
return;
}
Node* current = pq->head;
while (current != NULL) {
printf("(%d, %d) ", current->data, current->priority);
current = current->next;
}
printf("\n");
}
int main() {
PriorityQueue* pq = createPriorityQueue();
enqueue(pq, 5, 2);
enqueue(pq, 10, 1);
enqueue(pq, 3, 3);
printf("Priority queue: ");
display(pq);
printf("Dequeued element: %d\n", dequeue(pq));
printf("Priority queue after dequeue: ");
display(pq);
return 0;
}
Output:
Time complexity:
- The following operations have the following time complexity in C when a priority queue is implemented based on arrays:
Insertion-O (1)
Deletion-O (n)
Peek-O (n)
- A typical priority queue implementation is a binarized priority queue, commonly referred to as a binary heap. The following are the time complexities of several operations in a C binary heap-based priority queue:
Insertion-O (log n)
Deletion-O (log n)
Peek-O (1)
- A Fibonacci heap is a data structure that may be utilized to build a priority queue. For several activities, it provides practical time complexities. The following table lists the time complexity of several operations in a priority queue based on a Fibonacci heap in C:
Insertion-O (1)
Deletion-O (log n)
Peek-O (1)
- The temporal complexities of different operations in a priority queue built using a linked list are as follows:
Insertion-O (n)
Deletion-O (1)
Peek-O (1)
Features of the priority queue in C
- Ordering of Elements
- Priority-based Operations
- Unique Elements:
- Dynamic Size
- Efficient Operations:
- Choice of Implementations
- customizable Priority Function
Applications of Priority Queues in C
An effective way to get the element with the greatest priority is by priority queues, w data structures that store elements with associated priorities. They have applications in a variety of fields where effective prioritization and retrieval are essential. A few typical uses for priority queues are listed below:
- Task Scheduling: Priority queues are used in task scheduling algorithms. In these algorithms, each work is prioritized, and the scheduler retrieves and executes the job with the highest priority first.
- Priority queues may be employed in event-driven simulations, including discrete event simulation and event-driven gaming. The simulator handles the events in chronological sequence after queuing them depending on their time of occurrence.
- Dijkstra's Algorithm: Dijkstra's algorithm uses priority queues, a well-liked method for locating the shortest path in a graph. Vertex distances are stored in the priority queue, enabling the algorithm to choose the vertex with the smallest distance quickly.
- Priority queues are essential to the Huffman coding data compression process, which is used to compress data effectively. A binary tree is constructed using the priority queue to create the best prefix codes for effective compression, giving greater frequency characters a higher priority.
- Task Management: Systems for managing tasks, such as task schedulers or to-do lists, employ priority queues to organize jobs according to their relative importance. With the help of the priority queue, it is made sure that jobs with more significant priorities are carried out or shown first.
- Resource Allocation: When allocating resources with varied priority levels, priority queues can be employed. For instance, an operating system may employ a priority queue to manage CPU time or memory resources across several processes.
Advantages of Priority Queue in c
- Practical Priority-based activities:
Priority queues are made to manage Priority-based activities effectively. Priorities may be managed well by inserting an element with a priority and removing the one with the most significant priority with logarithmic time complexity.
- Flexible Data Structure:
Binary heaps, Fibonacci heaps, and balanced binary search trees are just a few examples of the many data structures that may be used to build priority queues. Because of this flexibility, programmers may select the best solution according to the particular needs of their application.
- Ordering of Elements:
Priority queues keep the elements in order according to their priorities. As a result, there is no need to manually sort or search through the entire data structure because the highest priority element is always available.
- Applications:
As was already said, priority queues have many different uses. They may be used for scheduling, event-driven simulations, graph algorithms, compression techniques, etc.
- Reduced Time Complexity:
Prioritization-based algorithms are less time-complex overall because of the efficient operations of a priority queue, such as the insertion and extraction of the highest priority element.