Priority Queues

Priority Queues in C++

A priority queue is a type of queue where each element is associated with a priority. Unlike a regular queue, where elements are processed in First In, First Out (FIFO) order, in a priority queue, elements are removed based on their priority, with the element of the highest priority being removed first.

Priority queues are typically implemented using heaps, particularly binary heaps. They are used in many algorithms, such as Dijkstra’s shortest path algorithm and Huffman coding, as well as in scenarios where tasks are handled based on priority, like in job scheduling systems.

Key Characteristics of a Priority Queue

1. Priority Order: Elements in a priority queue are always processed based on priority, not necessarily in the order they were added.

   • In a max-priority queue, the element with the highest priority (largest value) is dequeued first.
   • In a min-priority queue, the element with the lowest priority (smallest value) is dequeued first.

2. Heap-based Implementation: Priority queues are most commonly implemented using a heap. A heap is a binary tree where the key value at each node is greater than or equal to the values of its children (for a max heap) or smaller than or equal to the values of its children (for a min heap).

Basic Operations of a Priority Queue

1. Insert (Enqueue): Adds an element to the queue with a priority.
2. Extract-Max (or Extract-Min): Removes and returns the element with the highest (or lowest) priority.
3. Peek/Top: Returns the element with the highest (or lowest) priority without removing it.
4. IsEmpty: Checks if the priority queue is empty.
5. Size: Returns the number of elements currently in the queue.

Implementation of a Priority Queue in C++

C++ provides a built-in priority_queue class in the Standard Template Library (STL) that can be used to implement a priority queue efficiently. However, let's also discuss how you can implement a priority queue manually using a binary heap.

1. Using C++ STL priority_queue

The C++ Standard Template Library (STL) provides a priority_queue class that makes working with priority queues simple. By default, it implements a max-priority queue (the largest element has the highest priority).

STL Priority Queue Example:

#include <iostream>
#include <queue>
using namespace std;

int main() {
    // Create a max-priority queue (by default, the largest element has the highest priority)
    priority_queue<int> pq;

    pq.push(10);  // Insert elements
    pq.push(30);
    pq.push(20);
    pq.push(5);

    cout << "Top element: " << pq.top() << endl;  // Should print 30 (highest priority)

    pq.pop();  // Remove the element with the highest priority (30)

    cout << "Top element after pop: " << pq.top() << endl;  // Should print 20

    cout << "Is queue empty? " << (pq.empty() ? "Yes" : "No") << endl;  // Should print No

    return 0;
}

Customization of priority_queue

1. Min-Priority Queue: You can create a min-priority queue (where the smallest element has the highest priority) by using a custom comparator.

#include <iostream>
#include <queue>
using namespace std;

// Custom comparator for min-priority queue
struct Compare {
    bool operator()(int a, int b) {
        return a > b;  // This ensures the smallest element has the highest priority
    }
};

int main() {
    // Create a min-priority queue
    priority_queue<int, vector<int>, Compare> pq;

    pq.push(10);  // Insert elements
    pq.push(30);
    pq.push(20);
    pq.push(5);

    cout << "Top element (min-priority): " << pq.top() << endl;  // Should print 5 (lowest priority)

    pq.pop();  // Remove the element with the highest priority (5)

    cout << "Top element after pop: " << pq.top() << endl;  // Should print 10

    return 0;
}

2. Manual Implementation Using a Binary Heap

A priority queue can be efficiently implemented using a binary heap. A binary heap is a complete binary tree that satisfies the heap property:

• Max-Heap: In a max-heap, the parent’s value is greater than or equal to the values of its children.
• Min-Heap: In a min-heap, the parent’s value is less than or equal to the values of its children.

The heap is typically represented as an array, where:

• The root of the heap is at index 0.
• The left child of a node at index i is at index 2*i + 1.
• The right child of a node at index i is at index 2*i + 2.

Max-Heap Implementation of a Priority Queue:

#include <iostream>
#include <vector>
using namespace std;

class PriorityQueue {
private:
    vector<int> heap;  // The heap is stored in a vector

    // Helper function to maintain the max-heap property (heapify)
    void heapify(int index) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        // Find the largest among the root, left child, and right child
        if (left < heap.size() && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < heap.size() && heap[right] > heap[largest]) {
            largest = right;
        }

        // If the largest is not the root, swap and heapify the affected subtree
        if (largest != index) {
            swap(heap[index], heap[largest]);
            heapify(largest);
        }
    }

    // Helper function to insert a new element
    void insert(int value) {
        heap.push_back(value);  // Add the new element at the end
        int index = heap.size() - 1;

        // Fix the max-heap property if it is violated
        while (index != 0 && heap[(index - 1) / 2] < heap[index]) {
            swap(heap[(index - 1) / 2], heap[index]);
            index = (index - 1) / 2;
        }
    }

public:
    // Function to add an element to the priority queue
    void enqueue(int value) {
        insert(value);
    }

    // Function to remove and return the highest priority element
    int dequeue() {
        if (heap.size() == 0) {
            cout << "Queue is empty!" << endl;
            return -1;
        }

        // The root of the heap contains the highest priority element
        int root = heap[0];

        // Move the last element to the root and heapify
        heap[0] = heap[heap.size() - 1];
        heap.pop_back();
        heapify(0);

        return root;
    }

    // Function to return the highest priority element without removing it
    int top() {
        if (heap.size() == 0) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return heap[0];
    }

    // Function to check if the priority queue is empty
    bool isEmpty() {
        return heap.size() == 0;
    }
};

int main() {
    PriorityQueue pq;

    pq.enqueue(10);
    pq.enqueue(30);
    pq.enqueue(20);
    pq.enqueue(5);

    cout << "Top element (max-priority): " << pq.top() << endl;  // Should print 30

    pq.dequeue();  // Remove the element with the highest priority (30)

    cout << "Top element after dequeue: " << pq.top() << endl;  // Should print 20

    cout << "Is queue empty? " << (pq.isEmpty() ? "Yes" : "No") << endl;  // Should print No

    return 0;
}

Time Complexity of Priority Queue Operations

• Insert (Enqueue): O(log n), where n is the number of elements in the heap. This is because, in the worst case, we may need to "bubble up" an element from the bottom to the top of the heap.
• Extract-Max/Min (Dequeue): O(log n), as we need to "heapify" the heap to restore its properties after removing the root element.
• Top (Peek): O(1), as the highest (or lowest) priority element is always at the root of the heap.
• Size: O(1), as the size is maintained with a counter.
• IsEmpty: O(1), simply checks if the heap is empty.

Applications of Priority Queues

1. Task Scheduling: In systems like operating systems or real-time systems, tasks are scheduled based on priority, and priority queues are used to ensure that higher-priority tasks are executed first.

2. Dijkstra’s Shortest Path Algorithm: Priority queues are used to implement efficient shortest path algorithms, where the priority queue is used to manage the next node to visit based on the shortest known distance.

3. **H