Priority Queues (linked and array implementations of queues)

Priority Queue

A priority queue is an abstract data structure where each element has a priority associated with it. Elements are dequeued based on their priority rather than their order of insertion. In some cases, if two elements have the same priority, they follow the First In, First Out (FIFO) order, like a regular queue.

Key Operations:

1. Insert: Add an element with a priority.
2. Delete (Dequeue): Remove and return the element with the highest priority.
3. Peek/Top: Return the element with the highest priority without removing it.

Priority Queue Types:

1. Max Priority Queue: The element with the highest priority is dequeued first.
2. Min Priority Queue: The element with the lowest priority is dequeued first.

Priority Queue Implementations

There are two common ways to implement a priority queue: using arrays and linked lists.

1. Priority Queue Using Arrays

In the array-based implementation, elements are stored in an array, and the priority is managed by comparing values or using an auxiliary array for priorities.

C++ Code (Array Implementation):

#include <iostream>
using namespace std;

class PriorityQueue {
    int arr[5];    // Array to store elements
    int priority[5];  // Array to store priorities
    int size;

public:
    PriorityQueue() {
        size = 0;
    }

    // Function to insert an element with a priority
    void insert(int value, int pri) {
        if (size == 5) {
            cout << "Queue is full!\n";
            return;
        }

        arr[size] = value;
        priority[size] = pri;
        size++;
        cout << value << " inserted with priority " << pri << endl;
    }

    // Function to delete the highest priority element
    void deleteHighestPriority() {
        if (size == 0) {
            cout << "Queue is empty!\n";
            return;
        }

        int maxPriorityIdx = 0;
        for (int i = 1; i < size; i++) {
            if (priority[i] > priority[maxPriorityIdx]) {
                maxPriorityIdx = i;
            }
        }

        cout << "Element with value " << arr[maxPriorityIdx] << " and highest priority " << priority[maxPriorityIdx] << " dequeued.\n";

        // Shift elements
        for (int i = maxPriorityIdx; i < size - 1; i++) {
            arr[i] = arr[i + 1];
            priority[i] = priority[i + 1];
        }

        size--;
    }

    // Function to peek the highest priority element
    int peekHighestPriority() {
        if (size == 0) return -1;

        int maxPriorityIdx = 0;
        for (int i = 1; i < size; i++) {
            if (priority[i] > priority[maxPriorityIdx]) {
                maxPriorityIdx = i;
            }
        }

        return arr[maxPriorityIdx];
    }
};

int main() {
    PriorityQueue pq;
    pq.insert(10, 2);
    pq.insert(20, 5);
    pq.insert(30, 1);
    cout << "Highest priority element: " << pq.peekHighestPriority() << endl;
    pq.deleteHighestPriority();
    pq.deleteHighestPriority();
    return 0;
}

Time Complexity (Array-based Priority Queue):

• Insert: O(1) (simply appending the element to the end).
• Delete (Dequeue): O(n) (linear search for the highest priority).
• Peek: O(n) (linear search for the highest priority).

2. Priority Queue Using Linked List

In the linked list-based implementation, each node contains both the value and its priority. The nodes can either be inserted in a sorted order based on priority, or we can search for the highest priority element during dequeuing.

C++ Code (Linked List Implementation):

#include <iostream>
using namespace std;

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

class PriorityQueue {
    Node* head;

public:
    PriorityQueue() {
        head = NULL;
    }

    // Function to insert an element with priority
    void insert(int value, int pri) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->priority = pri;
        newNode->next = NULL;

        if (head == NULL || pri > head->priority) {
            newNode->next = head;
            head = newNode;
        } else {
            Node* temp = head;
            while (temp->next != NULL && temp->next->priority >= pri) {
                temp = temp->next;
            }
            newNode->next = temp->next;
            temp->next = newNode;
        }
        cout << value << " inserted with priority " << pri << endl;
    }

    // Function to delete the highest priority element
    void deleteHighestPriority() {
        if (head == NULL) {
            cout << "Queue is empty!\n";
            return;
        }

        Node* temp = head;
        head = head->next;
        cout << "Element with value " << temp->data << " and highest priority " << temp->priority << " dequeued.\n";
        delete temp;
    }

    // Function to peek the highest priority element
    int peekHighestPriority() {
        if (head == NULL) return -1;
        return head->data;
    }
};

int main() {
    PriorityQueue pq;
    pq.insert(10, 2);
    pq.insert(20, 5);
    pq.insert(30, 1);
    cout << "Highest priority element: " << pq.peekHighestPriority() << endl;
    pq.deleteHighestPriority();
    pq.deleteHighestPriority();
    return 0;
}

Time Complexity (Linked List-based Priority Queue):

• Insert: O(n) (inserting in a sorted position based on priority).
• Delete (Dequeue): O(1) (head node always has the highest priority).
• Peek: O(1) (highest priority is always at the head).

Comparison: Array vs. Linked List

Conclusion

• Array-based priority queues are simple to implement and offer fast insertion (O(1)) but are inefficient in dequeuing (O(n)).
• Linked list-based priority queues allow for faster dequeuing (O(1)) but require more time for insertion (O(n)) when maintaining the priority order.