What is a Priority Queue?

A priority queue in C++ is a special type of container adaptor that stores elements based on their priority rather than in a linear order (like a regular queue). In a priority queue, elements with higher priority are served before elements with lower priority. The priority is typically determined by the comparison logic provided by the user.

How Does Priority Queue Work?

Priority queues are implemented using a heap data structure internally, commonly a binary heap, which allows efficient retrieval of the highest (or lowest) priority element.

Components and Operations of Priority Queue:

1. Declaration: 

#include 

// Default: Max priority queue
priority_queue<int> pq;

// Min priority queue
priority_queue<int, vector<int>, greater<int>> pq;

2. Common Operations:

  • push(): Adds an element to the queue. 
pq.push(5);
pq.push(3);
pq.push(8);
  • pop(): Removes the highest priority element. 
pq.pop();
  • top(): Retrieves the highest priority element. 
int highest = pq.top();
  • empty(): Checks if the queue is empty. 
if(pq.empty()){
  cout << "Priority Queue is empty!";
}
  • size(): Returns the number of elements in the queue. 
int n = pq.size();

Understanding Comparators (greater and less):

greater:

  • Turns priority queue into a min priority queue.
  • Mechanism to remember: "greater comparator, smaller element first".
  • Why does this happen? Internally, the priority queue in C++ uses the comparator to maintain elements in the heap. The greater comparator defines that if the first element is greater than the second, it should appear later in the order. This means the smaller elements will bubble up to the top, making the smallest element have the highest priority.

less:

  • Turns priority queue into a max priority queue.
  • Mechanism to remember: "less comparator, larger element first".
  • Why does this happen? Similar to the greater comparator, less ensures that larger elements come first by pushing the smaller elements down in the heap structure.

Different Ways to Use Priority Queue:

1. Max Priority Queue (Default):

By default, priority queues in C++ are max-priority queues, meaning the largest element is given highest priority.

priority_queue<int> max_pq;
max_pq.push(2);
max_pq.push(10);
max_pq.push(5);

// Output: 10
cout << max_pq.top();

2. Min Priority Queue:

To create a min priority queue (smallest element has highest priority), use greater<> comparator:

priority_queue<int, vector<int>, greater<int>> min_pq;
min_pq.push(2);
min_pq.push(10);
min_pq.push(5);

// Output: 2
cout << min_pq.top();

3. Priority Queue with Custom Data Types:

You can define priority queues with custom data types:

struct Job {
  int priority;
  string task;

  bool operator<(const Job& other) const {
    return priority < other.priority;
  }
};

priority_queue<Job> jobQueue;

jobQueue.push({3, "Code Review"});
jobQueue.push({1, "Write Tests"});
jobQueue.push({2, "Bug Fixes"});

// Output: Code Review
cout << jobQueue.top().task;

Best Practices for Using Priority Queue:

1. Choosing the Right Comparator:

Always select the appropriate comparator (less for max priority, greater for min priority) or define your custom comparator clearly for custom data types.

2. Understand the Complexity:

  • push(): O(log n)
  • pop(): O(log n)
  • top(): O(1)

3. Avoid Frequent Modification:

Frequent modification (such as changing priorities) isn't efficient. If priorities change often, consider alternative structures.

4. Use with Custom Objects:

Clearly define the comparator in custom objects to avoid confusion about ordering.

5. Use Cases:

  • Dijkstra’s shortest path algorithm
  • Huffman encoding
  • Job scheduling algorithms
  • Maintaining median in running data stream

Example Usage in Problem-Solving (DSA Context):

Finding the K Largest Elements: 

vector<int> findKLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;

    for(int num : nums) {
        minHeap.push(num);
        if(minHeap.size() > k) {
            minHeap.pop();
        }
    }

    vector<int> result;
    while(!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    return result;
}

Conclusion:

Priority queues in C++ are powerful and versatile containers, ideal for problems involving prioritization. Understanding how they function internally, their operations, comparators, and appropriate scenarios will greatly enhance your problem-solving capabilities in data structures and algorithms.