Priority Queue

A Priority Queue is a special type of queue in which every element is assigned a priority. Elements are removed from the queue according to their priority rather than their insertion order.

• The element with higher priority is served first.
• If two elements have the same priority, they follow the FIFO (First In First Out) rule.

Unlike a normal queue, where deletion happens from the front only based on arrival order, a priority queue always processes the most important element first.

Real-Life Example

Consider a hospital emergency room:

• Critical patients are treated first.
• Less serious patients wait longer.

Even if a patient arrives later, they may get treatment earlier due to higher priority.

Types of Priority Queue

1. Ascending Priority Queue

In an ascending priority queue:

• Smaller priority number = higher priority
• Elements are removed in ascending order of priority number.

Example

Here, A will be removed first because it has the smallest priority value.

2. Descending Priority Queue

In a descending priority queue:

• Larger priority number = higher priority
• Elements are removed in descending order of priority number.

Example

Here, C will be removed first because it has the highest priority value.

Basic Operations of Priority Queue

1. Enqueue (Insertion)

Adds a new element with its priority into the queue.

Steps

1. Insert the element at the correct position according to priority.
2. Maintain priority order.

Example

Insert:

• A (Priority 2)
• B (Priority 5)
• C (Priority 1)

Queue becomes:

2. Dequeue (Deletion)

Removes the element with the highest priority.

Example

Before deletion:

After dequeue:

3. Peek

Displays the highest-priority element without removing it.

Example

Peek result = B

4. isEmpty()

Checks whether the queue contains elements or not.

• Returns True if queue is empty.
• Otherwise returns False.

5. isFull()

Checks whether the queue has reached maximum capacity.

Representation of Priority Queue

Priority Queue can be implemented using:

1. Arrays
2. Linked Lists
3. Heaps

Among these, Binary Heap is the most efficient and commonly used implementation.

Priority Queue Using Array

Two arrays are commonly used:

• One array stores data elements.
• Another array stores priorities.

Example

The highest-priority element remains at the front.

Algorithm for Enqueue

ENQUEUE(queue, priority, value, p)

1. If queue is full
      Print "Queue Overflow"
      Stop

2. Insert value into queue
3. Insert priority into priority array
4. Arrange elements according to priority

Algorithm for Dequeue

DEQUEUE(queue)

1. If queue is empty
      Print "Queue Underflow"
      Stop

2. Remove highest-priority element
3. Shift remaining elements

Applications of Priority Queue

Priority queues are widely used in computer science and real-world systems.

Common Applications

• CPU scheduling
• Printer management
• Dijkstra’s shortest path algorithm
• Huffman coding
• Network routing
• Event-driven simulation

Advantages of Priority Queue

• Processes important tasks first
• Efficient scheduling
• Useful in real-time systems
• Faster access to highest-priority element

Disadvantages of Priority Queue

• More complex than normal queue
• Insertion and deletion may take extra time
• Implementation can be difficult

Time Complexity

C Program for Priority Queue

#include <stdio.h>

#define SIZE 5

int data[SIZE];
int priority[SIZE];
int n = 0;

void enqueue(int value, int p) {
    if(n == SIZE) {
        printf("Queue is Full\n");
        return;
    }

    int i = n - 1;

    while(i >= 0 && priority[i] < p) {
        data[i + 1] = data[i];
        priority[i + 1] = priority[i];
        i--;
    }

    data[i + 1] = value;
    priority[i + 1] = p;
    n++;
}

void dequeue() {
    if(n == 0) {
        printf("Queue is Empty\n");
        return;
    }

    printf("Deleted Element = %d\n", data[0]);

    for(int i = 1; i < n; i++) {
        data[i - 1] = data[i];
        priority[i - 1] = priority[i];
    }

    n--;
}

void display() {
    for(int i = 0; i < n; i++) {
        printf("%d (Priority %d)\n", data[i], priority[i]);
    }
}

int main() {

    enqueue(10, 2);
    enqueue(50, 5);
    enqueue(20, 1);
    enqueue(40, 4);

    display();

    dequeue();

    printf("\nAfter Deletion:\n");

    display();

    return 0;
}

Output

50 (Priority 5)
40 (Priority 4)
10 (Priority 2)
20 (Priority 1)

Deleted Element = 50

After Deletion:
40 (Priority 4)
10 (Priority 2)
20 (Priority 1)