Priority Queue

A priority queue is a data structure that stores a collection of items with priorities and allows access to the item with the highest priority. The priority queue maintains the relative order of the items based on their priority values.

Operations of a Priority Queue:

Insert: Inserts an item with a priority value into the priority queue. The new item is placed in the correct position based on its priority value.

Delete: Removes the item with the highest priority from the priority queue.

Peek: Returns the item with the highest priority without removing it from the priority queue.

Real-life applications of Priority Queue:

Operating System Scheduling: Operating systems use priority queues to schedule processes. Each process is assigned a priority value and placed in a priority queue. The operating system then schedules the process with the highest priority to be executed first.

Emergency Room: In an emergency room, patients are assigned priority values based on the severity of their condition. The patients with the highest priority are treated first.

Network Traffic Management: Network traffic management systems use priority queues to prioritize traffic based on its type and importance. For example, video traffic may have a higher priority than email traffic.

Air Traffic Control: Air traffic control systems use priority queues to manage the takeoff and landing of airplanes. The airplanes are assigned priority values based on their flight schedule and the number of passengers on board.

Job Scheduling: Job scheduling systems use priority queues to prioritize the execution of jobs based on their priority values. Jobs with higher priority values are executed first.

Let us understand the implementation of priority queues :


#include <iostream>
using namespace std;

#define MAX_SIZE 100

class PriorityQueue {
private:
    int arr[MAX_SIZE];
    int size;
public:
    PriorityQueue() {
        size = 0;
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == MAX_SIZE;
    }

    void enqueue(int x) {
        if (isFull()) {
            cout << "Priority queue overflow!" << endl;
            return;
        }
        int i = size - 1;
        while (i >= 0 && x > arr[i]) {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = x;
        size++;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Priority queue underflow!" << endl;
            return -1;
        }
        int item = arr[size - 1];
        size--;
        return item;
    }

    int peek() {
        if (isEmpty()) {
            cout << "Priority queue is empty!" << endl;
            return -1;
        }
        return arr[size - 1];
    }
};

int main() {
    PriorityQueue pq;
    pq.enqueue(10);
    pq.enqueue(20);
    pq.enqueue(15);
    pq.enqueue(5);
    cout << pq.dequeue() << endl; // 20
    cout << pq.peek() << endl; // 15
    cout << pq.dequeue() << endl; // 15
    cout << pq.dequeue() << endl; // 10
    cout << pq.dequeue() << endl; // 5
    cout << pq.dequeue() << endl; // Priority queue underflow!
    return 0;
}

This implementation uses an array of size MAX_SIZE to store the elements of the priority queue, and the variable size to keep track of the current number of elements.

The functions isEmpty() and isFull() check if the priority queue is empty or full, respectively. The enqueue() function adds an element to the priority queue in the correct order, based on the priority of the element.

The dequeue() function removes and returns the element with the highest priority.

The peek() function returns the value of the element with the highest priority without removing it from the priority queue.

Finally, the main() function demonstrates the usage of the priority queue.

PRACTICE PROBLEMS :

Sliding Window maximum