priority_queue in C++

In C++, std::priority_queue is implemented as a max-heap by default. This means that the element with the highest priority (i.e., the maximum value according to the comparison function) is always at the top of the queue.

We can use the below initialization for a min-heap -

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

Difference between push & emplace

1. push:

   • Syntax: void push(const value_type& val);

   • Usage: Adds a copy of the given value to the priority queue.

   • Example:

     cppCopy codestd::priority_queue<int> pq;
     pq.push(10);
     pq.push(20);
     pq.push(5);

   • push takes a value of the type held by the priority queue and adds a copy of that value to the queue. It uses the copy constructor to create a new element and then adjusts the heap to maintain the priority order.

2. emplace:

   • Syntax: template <class... Args> void emplace(Args&&... args);

   • Usage: Constructs an element in-place within the priority queue.

   • Example:

     cppCopy codestd::priority_queue<std::pair<int, std::string>> pq;
     pq.emplace(10, "foo");
     pq.emplace(20, "bar");

   • emplace takes constructor arguments for the element type and constructs an element in-place within the priority queue. It's often more efficient than push because it avoids the extra copy construction step.

In summary, push is the simplest to use but involves copying elements into the priority queue. emplace constructs elements in-place and is often more efficient.

Efficiency

• Insertion (push/emplace): Inserting an element into a priority queue typically has a time complexity of O(log N), where N is the number of elements in the priority queue. This complexity arises from the need to maintain the heap property (heapify).

• Deletion (pop): Removing the highest-priority element also has a time complexity of O(log N) due to heap maintenance.

• Access (top): Accessing the highest-priority element is a constant-time operation (O(1)) since it's always at the front.

Use Cases and Examples

1. Finding the Kth Largest/Smallest Element: You can use a priority queue to efficiently find the Kth largest or smallest element in an array or stream of data.

   Example: Finding the 3rd largest element in an array.

   cppCopy codestd::priority_queue<int> maxHeap;
   int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
   for (int num : arr) {
       maxHeap.push(num);
       if (maxHeap.size() > 3) {
           maxHeap.pop();
       }
   }
   int thirdLargest = maxHeap.top();

2. Dijkstra's Shortest Path Algorithm: Priority queues are often used in graph algorithms like Dijkstra's algorithm to find the shortest path in a weighted graph.

   Example: Finding the shortest path in a weighted graph.

3. Task Scheduling: Priority queues can be used in scheduling tasks where tasks have different priorities, and you want to execute higher-priority tasks first.

   Example: Task scheduling with priorities.

4. Merge Sorted Lists: You can use a priority queue to merge multiple sorted lists efficiently.

   Example: Merging k sorted lists into one sorted list.

5. Solving Problems with Custom Priority: You can solve various problems by customizing the priority function based on the problem requirements.

   Example: Solving problems related to Huffman coding, finding the median in a stream of numbers, etc.