Implementing Priority Queues in C Programming

Table of Contents

1. [Fundamental Concepts](#fundamental - concepts)
2. [Implementing Priority Queues using Arrays](#implementing - priority - queues - using - arrays)
3. [Implementing Priority Queues using Linked Lists](#implementing - priority - queues - using - linked - lists)
4. [Usage Methods](#usage - methods)
5. [Common Practices](#common - practices)
6. [Best Practices](#best - practices)
7. Conclusion
8. References

Fundamental Concepts

What is a Priority Queue?

A priority queue is an abstract data type that follows the principle of prioritizing elements. It supports two main operations:

• Insertion: Adding an element to the priority queue along with its priority.
• Deletion: Removing the element with the highest priority from the priority queue.

Priority Queue Types

There are two types of priority queues:

• Max - Priority Queue: The element with the maximum priority is removed first.
• Min - Priority Queue: The element with the minimum priority is removed first.

Implementing Priority Queues using Arrays

Code Example

#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
    int data;
    int priority;
} Element;

Element queue[MAX_SIZE];
int rear = -1;

// Function to insert an element into the priority queue
void insert(int data, int priority) {
    if (rear == MAX_SIZE - 1) {
        printf("Queue is full!\n");
        return;
    }
    rear++;
    queue[rear].data = data;
    queue[rear].priority = priority;
    // Sort the queue based on priority
    for (int i = 0; i <= rear; i++) {
        for (int j = i + 1; j <= rear; j++) {
            if (queue[i].priority < queue[j].priority) {
                Element temp = queue[i];
                queue[i] = queue[j];
                queue[j] = temp;
            }
        }
    }
}

// Function to delete the element with the highest priority
int delete() {
    if (rear == -1) {
        printf("Queue is empty!\n");
        return -1;
    }
    int data = queue[0].data;
    for (int i = 0; i < rear; i++) {
        queue[i] = queue[i + 1];
    }
    rear--;
    return data;
}

// Function to display the priority queue
void display() {
    if (rear == -1) {
        printf("Queue is empty!\n");
        return;
    }
    for (int i = 0; i <= rear; i++) {
        printf("Data: %d, Priority: %d\n", queue[i].data, queue[i].priority);
    }
}

int main() {
    insert(10, 2);
    insert(20, 1);
    insert(30, 3);
    display();
    int deleted = delete();
    printf("Deleted element: %d\n", deleted);
    display();
    return 0;
}

Explanation

In this code, we use an array to implement a priority queue. The Element struct stores the data and its priority. The insert function adds an element to the queue and sorts the queue based on priority. The delete function removes the element with the highest priority. The display function shows all the elements in the queue.

Implementing Priority Queues using Linked Lists

Code Example

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    int priority;
    struct Node* next;
} Node;

Node* front = NULL;

// Function to insert an element into the priority queue
void insert(int data, int priority) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->priority = priority;
    if (front == NULL || priority > front->priority) {
        newNode->next = front;
        front = newNode;
    } else {
        Node* temp = front;
        while (temp->next != NULL && temp->next->priority >= priority) {
            temp = temp->next;
        }
        newNode->next = temp->next;
        temp->next = newNode;
    }
}

// Function to delete the element with the highest priority
int delete() {
    if (front == NULL) {
        printf("Queue is empty!\n");
        return -1;
    }
    Node* temp = front;
    int data = temp->data;
    front = front->next;
    free(temp);
    return data;
}

// Function to display the priority queue
void display() {
    if (front == NULL) {
        printf("Queue is empty!\n");
        return;
    }
    Node* temp = front;
    while (temp != NULL) {
        printf("Data: %d, Priority: %d\n", temp->data, temp->priority);
        temp = temp->next;
    }
}

int main() {
    insert(10, 2);
    insert(20, 1);
    insert(30, 3);
    display();
    int deleted = delete();
    printf("Deleted element: %d\n", deleted);
    display();
    return 0;
}

Explanation

Here, we use a linked list to implement a priority queue. The Node struct represents a node in the linked list, containing data, priority, and a pointer to the next node. The insert function inserts a new node in the correct position based on its priority. The delete function removes the node with the highest priority, and the display function shows all the nodes in the queue.

Usage Methods

• Initialization: Initialize the priority queue before using it. For an array - based implementation, set the rear pointer to -1. For a linked - list - based implementation, set the front pointer to NULL.
• Insertion: Use the insert function to add elements to the priority queue. Provide the data and its priority as parameters.
• Deletion: Use the delete function to remove the element with the highest priority from the queue.
• Display: Use the display function to view all the elements in the priority queue.

Common Practices

• Error Handling: Always check if the queue is full before inserting an element and if the queue is empty before deleting an element.
• Sorting: When using an array - based implementation, sort the queue after each insertion to ensure that the element with the highest priority is at the front.
• Memory Management: In a linked - list - based implementation, use malloc to allocate memory for new nodes and free to release the memory when deleting nodes.

Best Practices

• Use Heaps: Heaps are a more efficient data structure for implementing priority queues. A binary heap can perform insertion and deletion operations in $O(log n)$ time complexity, compared to $O(n)$ for an array - based implementation.
• Modular Design: Break the code into smaller functions for better readability and maintainability. Each function should have a single responsibility, such as insertion, deletion, or display.

Conclusion

Implementing priority queues in C can be done using arrays or linked lists. Each method has its own advantages and disadvantages. Array - based implementations are simple but may require sorting after each insertion, which can be time - consuming. Linked - list - based implementations are more flexible and can insert elements in the correct position without sorting the entire list. By following the usage methods, common practices, and best practices mentioned in this blog, you can effectively implement and use priority queues in your C programs.

References

• “Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
• GeeksforGeeks - https://www.geeksforgeeks.org/priority-queue-set-1-introduction/
• TutorialsPoint - https://www.tutorialspoint.com/data_structures_algorithms/priority_queue.htm