Chapter 10 – Priority Queues

Chapter 10: Priority Queues

---

Welcome to Chapter 10! In this chapter, we’ll explore Priority Queues, a special type of queue where elements are processed based on their priority rather than the order in which they were added. Priority queues are incredibly useful in various real-world applications, such as task scheduling, Dijkstra’s shortest path algorithm, and handling network packets.

Let’s dive into the concept and understand how they work!

---

What is a Priority Queue?

A Priority Queue is a data structure where each element is associated with a priority, and the element with the highest (or lowest) priority is dequeued first. Unlike a regular queue, which follows the First-In-First-Out (FIFO) principle, priority queues can rearrange the order of processing based on priorities.

For example, in an emergency room, patients with life-threatening conditions (higher priority) will be treated first, even if they arrived after other patients with minor injuries.

Here’s a basic visual of how a priority queue works:

Priority Queue:
[Critical Patient (Priority 3)] -> [Moderate Patient (Priority 2)] -> [Minor Patient (Priority 1)]

In this case, the Critical Patient will be dequeued and treated first, regardless of the order in which they entered the queue.

---

Types of Priority Queues

There are two types of priority queues:

1. Max-Priority Queue: In this type, the element with the highest priority is dequeued first.

2. Min-Priority Queue: In this type, the element with the lowest priority is dequeued first.

For instance, in task scheduling systems at Emancipation Edutech Private Limited, a max-priority queue might be used to prioritize the most urgent student requests first.

---

Priority Queue Operations

The following operations are performed on priority queues:

1. Insert (Enqueue): Add an element to the queue with a given priority.

2. Extract Max (Dequeue): Remove the element with the highest priority (in max-priority queues).

3. Get Max: Retrieve, but do not remove, the element with the highest priority.

4. Increase Priority: Change the priority of an element in the queue.

Let’s understand these operations more deeply by implementing a priority queue using arrays.

---

Priority Queue Implementation Using Arrays

To keep things simple, we’ll implement a max-priority queue using arrays, where higher numbers indicate higher priorities.

Define the Queue Structure

#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // Max size of the priority queue

struct PriorityQueue {
    int data[MAX]; // Array to store elements
    int priority[MAX]; // Array to store priorities
    int size; // Number of elements in the queue
};

• data: Stores the elements.
• priority: Stores the priority associated with each element.
• size: Tracks the current number of elements in the queue.

Initialize the Priority Queue

void initialize(struct PriorityQueue* pq) {
    pq->size = 0; // Queue is initially empty
}

Insert Operation

void insert(struct PriorityQueue* pq, int value, int prio) {
    if (pq->size == MAX) { // Check if the queue is full
        printf("Queue Overflow\n");
        return;
    }
    
    int i = pq->size;
    pq->data[i] = value;
    pq->priority[i] = prio;
    pq->size++;
}

Here, we simply insert an element along with its priority at the end of the queue.

Extract Max Operation

int extractMax(struct PriorityQueue* pq) {
    if (pq->size == 0) { // Check if the queue is empty
        printf("Queue Underflow\n");
        return -1;
    }
    
    int maxIndex = 0;
    
    // Find the element with the highest priority
    for (int i = 1; i < pq->size; i++) {
        if (pq->priority[i] > pq->priority[maxIndex]) {
            maxIndex = i;
        }
    }
    
    int maxValue = pq->data[maxIndex]; // Store the highest priority value
    
    // Shift the remaining elements
    for (int i = maxIndex; i < pq->size - 1; i++) {
        pq->data[i] = pq->data[i + 1];
        pq->priority[i] = pq->priority[i + 1];
    }
    
    pq->size--;
    
    return maxValue;
}

In this operation, we scan the queue to find the element with the highest priority and then remove it, shifting the rest of the elements.

Example Usage

int main() {
    struct PriorityQueue pq;
    initialize(&pq);

    // Insert elements with priorities
    insert(&pq, 10, 1);  // Insert value 10 with priority 1
    insert(&pq, 20, 4);  // Insert value 20 with priority 4
    insert(&pq, 30, 3);  // Insert value 30 with priority 3
    
    // Extract the highest priority element
    printf("Extracted element: %d\n", extractMax(&pq));
    
    return 0;
}

Output:

Extracted element: 20

Notice how 20 was extracted because it had the highest priority (4).

---

Using Priority Queues in Real Life

Priority queues are extremely useful in real-world applications. Let’s explore some common scenarios:

1. Task Scheduling: Operating systems use priority queues to manage tasks. Processes with higher priority are executed before lower-priority processes, ensuring time-sensitive tasks are handled quickly.

2. Network Traffic: In network systems, priority queues help manage data packets. Critical packets (such as emergency notifications) are transmitted first, while less important packets (like email) are handled later.

3. Dijkstra’s Algorithm: Priority queues are used in algorithms like Dijkstra’s Shortest Path Algorithm. Nodes with the smallest distance (priority) are processed first, helping to find the shortest path between two points efficiently.

4. Emergency Systems: Priority queues manage patients in hospitals, where the most critical patients (with higher priorities) are treated first.

At Emancipation Edutech Private Limited, we could use priority queues to manage student queries or schedule courses based on demand, ensuring that high-demand courses are given priority. Don’t forget to explore digilearn.cloud to access more free educational resources!

---

Implementing Priority Queues Using Heaps

While arrays are a simple way to implement priority queues, they’re not the most efficient. For faster access to the highest-priority element, heaps are commonly used. A binary heap allows both insertion and extraction of the maximum element in O(log n) time, compared to O(n) time with arrays.

Let’s see how a max-heap works with priority queues:

Max-Heap Representation

A max-heap is a binary tree where the parent node is always greater than or equal to its children. This ensures that the root always contains the highest-priority element, which can be removed efficiently.

       20
      /  \
     15   10
    /  \
   8    5

Here, 20 is the maximum value, and extracting it will require only O(log n) time to rearrange the heap.

---

Applications of Priority Queues

Priority queues are widely used in areas like:

1. Operating Systems: For task scheduling and resource management.
2. Graph Algorithms: In shortest path algorithms, where nodes with the lowest cost are processed first.
3. Simulation Systems: To manage events that need to be processed in a particular order.
4. Airline Reservation Systems: Where priority passengers are processed first.

---

Advantages and Disadvantages of Priority Queues

Advantages:

• Flexible Processing: Priority queues allow for flexible processing by letting you prioritize critical tasks over non-critical ones.
• Efficient for Scheduling: They are essential in scheduling systems, ensuring high-priority tasks are handled in a timely manner.

Disadvantages:

• Complexity: Priority queues implemented with heaps can be harder to understand and manage for beginners.
• Slow with Arrays: Array-based implementations are slower for large datasets, requiring more efficient structures like heaps.

---

Conclusion

Priority queues are a powerful data structure, essential for managing tasks with different priorities. By mastering priority queues, you’ll be better equipped to handle real-world problems like scheduling and resource management.

In the next chapter, we will explore Deques (Double-Ended Queues), where elements can be added and removed from both ends.

Keep practicing, and as always, stay curious!

---

Next Chapter: Deques (Double-Ended Queues)