C++ priority queues

---

Introduction

In C++, a priority queue is a type of container adaptor in the C++ Standard Library that allows elements to be processed in a specific order based on their priority. This data structure is a heap-based container, which is implemented in the <queue> header. A priority queue orders its elements in such a way that the highest (or lowest) priority element is always accessible at the top. By default, C++ uses a max-heap implementation, where the largest element has the highest priority.

Key Features of std::priority_queue

• Max-Heap by Default: Elements in a std::priority_queue are ordered so that the largest (or highest priority) element is at the top of the container.
• Efficient Access to Top Element: The top element can be accessed and removed efficiently, making the priority queue suitable for tasks that need to process the highest priority element first.
• Dynamic Priority Assignment: The priority queue maintains the order based on the priority defined either by default (greater priority for larger elements) or through custom comparison logic.
• Under-the-Hood Implementation: Typically, the C++ priority_queue is implemented using a binary heap structure, which provides an efficient way to manage the order.

---

Syntax

To declare a priority queue:

std::priority_queue<T> pq;

Where:

• T is the type of elements in the priority queue (e.g., int, std::string).

You can also define the container with a custom comparison function to change the priority order:

std::priority_queue<T, Container, Compare> pq;

Where:

• Container is the underlying container type (like std::vector by default).
• Compare is a binary function or a comparison object that defines the ordering.

---

Declaring and Initializing a Priority Queue

Example 1: Basic Priority Queue Declaration

#include <iostream>
#include <queue>

int main() {
    // Declare a priority queue of integers (max-heap by default)
    std::priority_queue<int> pq;

    // Insert elements into the priority queue
    pq.push(10);
    pq.push(20);
    pq.push(15);

    // Displaying the top element
    std::cout << "Top element: " << pq.top() << std::endl;  // Output: 20

    return 0;
}

Explanation:

• push() adds elements to the priority queue.
• top() accesses the element with the highest priority (the largest in a max-heap).

---

Custom Comparison: Min-Heap Priority Queue

By default, the std::priority_queue implements a max-heap, where the largest element has the highest priority. However, you can change this behavior to implement a min-heap by providing a custom comparator.

Example 2: Min-Heap Priority Queue (Custom Comparison)

#include <iostream>
#include <queue>
#include <vector>
#include <functional>  // For std::greater

int main() {
    // Declare a priority queue with min-heap (using std::greater)
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    // Insert elements into the priority queue
    pq.push(10);
    pq.push(20);
    pq.push(15);

    // Displaying the top element (smallest element in min-heap)
    std::cout << "Top element: " << pq.top() << std::endl;  // Output: 10

    return 0;
}

Explanation:

• By using std::greater<int>, the priority queue behaves like a min-heap, where the smallest element has the highest priority.

---

Important Member Functions of std::priority_queue

1. push()

• Adds an element to the priority queue.

pq.push(30);  // Adds 30 to the priority queue

2. pop()

• Removes the element with the highest priority from the top of the priority queue.

pq.pop();  // Removes the element with the highest priority (top element)

3. top()

• Returns the element with the highest priority (top element).

std::cout << "Top element: " << pq.top() << std::endl;

4. size()

• Returns the number of elements in the priority queue.

std::cout << "Size of the priority queue: " << pq.size() << std::endl;

5. empty()

• Checks if the priority queue is empty.

if (pq.empty()) {
    std::cout << "The priority queue is empty!" << std::endl;
} else {
    std::cout << "The priority queue is not empty!" << std::endl;
}

---

Iterating Through a Priority Queue

Unlike other containers such as vectors or lists, you cannot directly iterate through a std::priority_queue since it is a container adaptor designed to give access only to the top element. However, you can pop elements from the queue to process them one by one.

Example 1: Iterating by Popping Elements

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(10);
    pq.push(20);
    pq.push(15);

    // Process elements by popping from the queue
    while (!pq.empty()) {
        std::cout << pq.top() << " ";  // Display the top element
        pq.pop();  // Remove the top element
    }

    return 0;
}

 Output:

20 15 10

Explanation:

• Elements are processed and removed in order of their priority (largest to smallest in a max-heap).

---

Advantages of std::priority_queue

1. Efficient Access to the Top Element: The top() function allows constant-time access to the highest priority element, making priority queues ideal for scheduling and decision-making tasks.
2. Heap Operations: Internally, the priority queue uses a heap structure, allowing insertions and deletions to be performed efficiently in O(log n) time.
3. Customizable Priority: By providing a custom comparator, you can easily change the priority behavior from max-heap to min-heap or even implement more complex ordering.
4. Dynamic Size: Like other container adaptors, std::priority_queue grows dynamically as elements are added.

---

When to Use std::priority_queue

Use a priority queue when:

• You need to repeatedly access the element with the highest (or lowest) priority.
• You want to process elements in order of their priority, such as in scheduling tasks or managing events in simulation systems.
• You need a structure where the order of processing is dynamic but defined by the value of the elements.

---

Real-World Applications of Priority Queues

1. Task Scheduling: Operating systems use priority queues to schedule tasks based on their priority (e.g., CPU scheduling, disk scheduling).
2. Dijkstra's Algorithm: In shortest-path algorithms like Dijkstra’s, a priority queue is used to select the node with the smallest distance efficiently.
3. Huffman Encoding: In data compression algorithms, a priority queue is used to build a Huffman tree where the least frequent elements have lower priority.
4. Event Simulation: Priority queues are used in event-driven simulation systems, where events are processed in order of their time or priority.

---

---