Priority Queue: Container, C++

In C++, the priority_queue container is part of the Standard Template Library (STL) and allows you to manage a collection of elements where each element has a priority. Unlike queue, where elements are processed in a First-In-First-Out (FIFO) manner, elements in a priority_queue are ordered based on their priority, with the highest priority element always at the top.

This guide will walk you through the different ways to construct a priority queue, how to perform common operations like push, pop, top, empty, and size, and how to use custom comparison logic to tailor the priority queue for different scenarios.

Table of Contents

1. Introduction to Priority Queue in C++
2. Different Ways to Construct a Priority Queue
3. Common Operations on Priority Queue
   • push()
   • pop()
   • top()
   • empty()
   • size()
4. Working with Custom Comparison Logic
5. Working with Custom Data Types
6. Summary and Best Practices

1. Introduction to Priority Queue in C++

In C++, a priority_queue is an adaptor container that maintains a collection of elements where the element with the highest priority is always at the top. The priority queue is typically implemented using a heap (a binary heap is the most common) and offers logarithmic time complexity for inserting elements and removing the top element.

Key Features:

• Push: Adds an element to the priority queue while maintaining the order.
• Pop: Removes the top element (the one with the highest priority).
• Top: Retrieves the top element without removing it.
• Empty: Checks if the priority queue is empty.
• Size: Returns the number of elements in the queue.

2. Different Ways to Construct a Priority Queue

The priority_queue in C++ is flexible, allowing you to construct it in different ways, depending on the underlying container and how you want to define the element priority. By default, a priority_queue uses vector as its underlying container, but you can also use deque if needed.

2.1 Default Constructor

By default, the priority_queue uses a max-heap, meaning the largest element has the highest priority and is placed at the top. It uses a vector as the underlying container.

priority_queue<int> pq;

In this example, pq is an empty priority queue of integers, and it is implemented as a max-heap using a vector internally.

2.2 Constructor with Initial Container

You can initialize a priority_queue by passing an existing container such as vector, deque, or array to the constructor. The queue is initialized by passing the iterators (using .begin() and .end()).

Example with vector:

vector<int> v = {10, 20, 15, 30, 40};
priority_queue<int> pq(v.begin(), v.end());

In this case, the priority queue pq is initialized with the elements of the vector v.

Example with deque:

deque<int> d = {10, 20, 15, 30, 40};
priority_queue<int, deque<int>> pq(d.begin(), d.end());

Here, the priority_queue pq is initialized with the elements of the deque d. While the default underlying container for a priority_queue is a vector, you can explicitly specify deque as the underlying container if you prefer.

Example with an array:

int arr[] = {10, 20, 15, 30, 40};
priority_queue<int> pq(arr, arr + 5); // Using array and iterators

In this case, the priority queue pq is initialized using an array arr. We use the array's iterators to initialize the queue.

2.3 Custom Comparator (Min-Heap)

By default, the priority_queue uses a max-heap (where the largest element has the highest priority). However, you can change this behavior by specifying a custom comparator. For example, if you want to use a min-heap (smallest element has the highest priority), you can do so by passing a greater<T> comparator.

priority_queue<int, vector<int>, greater<int>> pq;

This creates a min-heap, where the smallest element is given the highest priority. The underlying container in this case is vector, but you could also use deque in the same way if needed.

2.4 Custom Comparator Using Function Objects

If you want more control over how elements are compared, you can define a custom comparator using function objects (functors). This is useful when dealing with complex types or when you need specific comparison logic.

struct CustomComparator {
    bool operator()(const int& a, const int& b) {
        return a > b;  // Smaller elements will have higher priority (min-heap)
    }
};

priority_queue<int, vector<int>, CustomComparator> pq;

In this example, the CustomComparator functor makes smaller elements have higher priority, effectively turning the priority queue into a min-heap. The underlying container is vector, but as mentioned earlier, you can also use deque.

3. Common Operations on Priority Queue

3.1 push()

The push() function adds an element to the priority queue while maintaining the priority order.

Syntax:

pq.push(element);

Example:

priority_queue<int> pq;
pq.push(10);
pq.push(20);
pq.push(15);

After this, the priority queue pq will have the following order: 20 (top), 15, 10 (bottom).

3.2 pop()

The pop() function removes the top element (the one with the highest priority) from the priority queue.

Syntax:

pq.pop();

Example:

priority_queue<int> pq;
pq.push(10);
pq.push(20);
pq.push(15);
pq.pop();  // Removes 20

After calling pop(), the new top element will be 15.

3.3 top()

The top() function retrieves the top element of the priority queue without removing it.

Syntax:

element = pq.top();

Example:

priority_queue<int> pq;
pq.push(10);
pq.push(20);
pq.push(15);
cout << "Top element: " << pq.top() << endl;  // Outputs: 20

3.4 empty()

The empty() function checks whether the priority queue is empty.

Syntax:

bool isEmpty = pq.empty();

Example:

priority_queue<int> pq;
cout << "Is the priority queue empty? " << (pq.empty() ? "Yes" : "No") << endl;  // Outputs: Yes
pq.push(10);
cout << "Is the priority queue empty? " << (pq.empty() ? "Yes" : "No") << endl;  // Outputs: No

3.5 size()

The size() function returns the number of elements in the priority queue.

Syntax:

size_t queueSize = pq.size();

Example:

priority_queue<int> pq;
pq.push(10);
pq.push(20);
cout << "Priority queue size: " << pq.size() << endl;  // Outputs: 2

4. Working with Custom Comparison Logic

The true power of priority_queue comes when you can specify a custom comparison logic for how elements should be prioritized. This allows you to easily implement both min-heaps and custom sorting mechanisms.

Example: Min-Heap Using greater<T>

priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(10);
minHeap.push(20);
minHeap.push(5);
cout << "Top of Min-Heap: " << minHeap.top() << endl;  // Outputs: 5

In this example, the smallest element (5) is at the top, implementing a min-heap.

Example: Custom Comparator for Complex Types

For more complex data types, you can use custom comparators to sort based on specific conditions.

struct Person {
    string name;
    int age;

    Person(string n, int a) : name(n), age(a) {}
};

struct CompareByAge {
    bool operator()(const Person& p1, const Person& p2) {
        return p1.age > p2.age;  // Older people have lower priority
    }
};

priority_queue<Person, vector<Person>, CompareByAge> pq;
pq.push(Person("Alice", 30));
pq.push(Person("Bob", 25));
pq.push(Person("Charlie", 35));

cout << "Top person by age: " << pq.top().name << endl;  // Outputs: Bob

In this case, the CompareByAge comparator ensures that the person with the lowest age will have the highest priority.

5. Working with Custom Data Types

priority_queue can also store custom data types. By combining custom comparison logic with user-defined types, you can implement advanced priority structures. Below is an example of how to use priority_queue with custom objects.

Example: Priority Queue of Custom Objects

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

class Task {
public:
    string taskName;
    int priority;

    Task(string name, int p) : taskName(name), priority(p) {}

    void display() const {
        cout << "Task: " << taskName << ", Priority: " << priority << endl;
    }
};

struct TaskComparator {
    bool operator()(const Task& t1, const Task& t2) {
        return t1.priority < t2.priority;  // Higher priority tasks have higher priority
    }
};

int main() {
    priority_queue<Task, vector<Task>, TaskComparator> taskQueue;

    taskQueue.push(Task("Task 1", 2));
    taskQueue.push(Task("Task 2", 1));
    taskQueue.push(Task("Task 3", 3));

    while (!taskQueue.empty()) {
        taskQueue.top().display();  // Display top task
        taskQueue.pop();            // Remove the top task
    }

    return 0;
}

In this example, the tasks are ordered based on their priority, with higher priority tasks appearing at the top.

6. Summary and Best Practices

• Queue Construction: You can construct a priority queue using the default constructor, by passing an existing container, or by specifying a custom comparator for more flexible behavior.
• Operations: Use push() to add elements, pop() to remove the top element, top() to view the highest-priority element, empty() to check if the queue is empty, and size() to get the number of elements.
• Custom Comparators: You can use custom comparators to create min-heaps or implement other specific ordering logic.
• Custom Data Types: Priority queues can store and manage custom data types, which makes them ideal for complex applications like task scheduling or event-driven systems.

Best Practices:

1. Minimize Overhead: Avoid unnecessary copying of large objects by using references or pointers in custom comparators.
2. Use Correct Comparators: Ensure the comparator properly reflects your intended order. For example, use greater<T> for a min-heap and less<T> for a max-heap.
3. Empty Check Before Pop: Always check if the priority queue is empty using empty() before calling pop() to avoid undefined behavior.

The priority_queue container in C++ is a highly useful tool for managing elements based on priority. Whether you're dealing with scheduling tasks, simulating events, or simply managing elements in order, the priority_queue provides an efficient and flexible way to handle these situations. By understanding its construction and operation, as well as how to leverage custom comparison logic, you can unlock its full potential in your C++ programs.