Priority Queue in C++ STL

AL NAFIS FUAD SHUVOAL NAFIS FUAD SHUVO
7 min read

Table of contents

DESCRIPTION

  • A container that represents a priority queue, implementing a binary heap to maintain elements in a specific order (max heap or min heap).

  • Follows the priority queue principle, where the element with the highest or lowest priority is served before others.

  • Suitable for scenarios where elements need to be processed in order of priority.

ALL THE POSSIBLE WAYS TO DECLARE, INITIALIZE AND PRINTING PRIORITY QUEUE:

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // Declaration of max heap
    priority_queue<int> maxHeap;

    // Declaration of min heap
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Initializing heaps using push
    maxHeap.push(30);
    maxHeap.push(10);
    maxHeap.push(20);

    minHeap.push(30);
    minHeap.push(10);
    minHeap.push(20);

    // Printing max heap using while loop and top
    cout << "Max Heap Contents (top to bottom): ";
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    cout << endl;

    // Printing min heap using while loop and top
    cout << "Min Heap Contents (top to bottom): ";
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;

    return 0;
}

OUTPUT:


Max Heap Contents (top to bottom): 30 20 10
Min Heap Contents (top to bottom): 10 20 30

MEMBER FUNCTIONS:

  1. Empty:

    • Works: Returns whether the priority queue is empty.

    • Syntax: myPriorityQueue.empty()

    • Example:

        priority_queue<int> myPriorityQueue;
  bool isEmpty = myPriorityQueue.empty();

  2. Size:

    • Works: Returns the number of elements in the priority queue.

    • Syntax: myPriorityQueue.size()

    • Example:

        priority_queue<int> myPriorityQueue = {3, 1, 4, 1, 5, 9};
  size_t queueSize = myPriorityQueue.size();

  3. Top:

    • Works: Returns a reference to the top element (max element in max heap, min element in min heap).

    • Syntax: myPriorityQueue.top()

Example:

priority_queue<int> myPriorityQueue = {3, 1, 4, 1, 5, 9};
int topElement = myPriorityQueue.top();

CODE:

#include <iostream>
#include <queue>

using namespace std;

int main() {
    // Priority queue representing a max heap
    priority_queue<int> maxHeap;

    // Function to check if the priority queue is empty
    auto isEmpty = [&]() {
        return maxHeap.empty();
    };

    // Function to get the number of elements in the priority queue
    auto getSize = [&]() {
        return maxHeap.size();
    };

    // Function to get a reference to the top element
    auto getTop = [&]() {
        return maxHeap.top();
    };

    // Example usage
    maxHeap.push(10);
    maxHeap.push(5);
    maxHeap.push(20);

    cout << "Size of priority queue: " << getSize() << endl;
    cout << "Top element: " << getTop() << endl;

    maxHeap.pop();

    cout << "After popping, top element: " << getTop() << endl;

    return 0;
}

OUTPUT:

Size of priority queue: 3
Top element: 20
After popping, top element: 10

MODIFIERS:

  1. Push:

    • Works: Adds an element to the priority queue.

    • Syntax: myPriorityQueue.push(value)

    • Example:

        priority_queue<int> myPriorityQueue;
  myPriorityQueue.push(42);

  2. Pop:

    • Works: Removes the top element from the priority queue.

    • Syntax: myPriorityQueue.pop()

    • Example:

priority_queue<int> myPriorityQueue = {3, 1, 4, 1, 5, 9};
myPriorityQueue.pop();

CODE:

#include <iostream>
#include <queue>

using namespace std;

int main() {
    // Priority queue representing a max heap
    priority_queue<int> maxHeap;

    // Example usage
    maxHeap.push(10);
    maxHeap.push(5);
    maxHeap.push(20);

    cout << "Size of priority queue: " << maxHeap.size() << endl;
    cout << "Top element: " << maxHeap.top() << endl;

    maxHeap.pop();

    cout << "After popping, top element: " << maxHeap.top() << endl;

    return 0;
}

OUTPUT:

Size of priority queue: 3
Top element: 20
After popping, top element: 10

ALGORITHM

ALGORITHMS DIRECTLY APPLICABLE TO PRIORITY QUEUES:

1. Max:

  • Works: Returns the greater of two values.

  • Syntax: Priority_queue is a container adapter, and direct comparison is not available. To get the maximum element, you can access the top element of the priority_queue.

    Example:

      cppCopy code// Example:
  priority_queue<int> myPriorityQueue = {5, 8, 2};
  int largerValue = myPriorityQueue.top();

2. Max Element:

  • Works: Finds the largest element in a range.

  • Syntax: Max_element is not directly applicable to priority_queue. To get the maximum element, you can access the top element of the priority_queue.

    Example:

      cppCopy code// Example:
  priority_queue<int> myPriorityQueue = {3, 7, 2, 8, 5};
  int maxElement = myPriorityQueue.top();

3. Min:

  • Works: Returns the smaller of two values.

  • Syntax: Priority_queue is a container adapter, and direct comparison is not available. To get the minimum element, you need to customize the comparison by using a min heap.

    Example:

      cppCopy code// Example:
  priority_queue<int, vector<int>, greater<int>> myMinPriorityQueue = {5, 8, 2};
  int smallerValue = myMinPriorityQueue.top();

4. Min Element:

  • Works: Finds the smallest element in a range.

  • Syntax: Min_element is not directly applicable to priority_queue. To get the minimum element, you need to customize the comparison by using a min heap.

    Example:

      cppCopy code// Example:
  priority_queue<int, vector<int>, greater<int>> myMinPriorityQueue = {3, 7, 2, 8, 5};
  int minElement = myMinPriorityQueue.top();

5. Accumulate:

  • Works: Accumulates the result of an operation on a sequence.

  • Syntax: Priority_queue is not directly applicable to accumulate. You may need to iterate through the priority_queue to accumulate the values.

    Example:

      cppCopy code// Example:
  priority_queue<int> myPriorityQueue = {3, 7, 2, 8, 5};
  int sum = 0;
  while (!myPriorityQueue.empty()) {
      sum += myPriorityQueue.top();
      myPriorityQueue.pop();
  }

CODE:

  •   #include <iostream>
  #include <vector>
  #include <queue>
  #include <algorithm>

  using namespace std;

  int main() {
      // Example for Max
      priority_queue<int> myPriorityQueueMax = {5, 8, 2};
      int largerValue = myPriorityQueueMax.top();
      cout << "Max Value: " << largerValue << endl;

      // Example for Max Element
      priority_queue<int> myPriorityQueueMaxElement = {3, 7, 2, 8, 5};
      int maxElement = myPriorityQueueMaxElement.top();
      cout << "Max Element: " << maxElement << endl;

      // Example for Min
      priority_queue<int, vector<int>, greater<int>> myMinPriorityQueue = {5, 8, 2};
      int smallerValue = myMinPriorityQueue.top();
      cout << "Min Value: " << smallerValue << endl;

      // Example for Min Element
      priority_queue<int, vector<int>, greater<int>> myMinPriorityQueueElement = {3, 7, 2, 8, 5};
      int minElement = myMinPriorityQueueElement.top();
      cout << "Min Element: " << minElement << endl;

      // Example for Accumulate
      priority_queue<int> myAccumulatePriorityQueue = {3, 7, 2, 8, 5};
      int sum = 0;
      while (!myAccumulatePriorityQueue.empty()) {
          sum += myAccumulatePriorityQueue.top();
          myAccumulatePriorityQueue.pop();
      }
      cout << "Accumulated Sum: " << sum << endl;

      return 0;
  }

    OUTPUT:

Max Value: 8
Max Element: 8
Min Value: 2
Min Element: 2
Accumulated Sum: 25

N.B: ALGORITHMS NOT DIRECTLY APPLICABLE TO QUEUES:

  1. Binary Search:

    • Binary search relies on accessing elements at the middle of a sorted collection, which is not efficiently supported by priority queues. Priority queues are typically implemented using heaps, and accessing elements in the middle doesn't have a straightforward interpretation in the context of a priority queue.

  2. equal_range():

    • Similar to binary search, equal_range() needs random access, which is not guaranteed in a priority queue. To find a range of elements with a given priority value, you might need to iterate through the priority queue and maintain a range of elements matching the desired priority value.

  3. inplace_merge():

    • In-place merging involves merging two sorted ranges without additional memory allocations. This operation is challenging with queues, as they are not inherently sorted. If sorting is a requirement, you might need to use a different data structure or consider sorting the priority queue before attempting an in-place merge.

  4. lower_bound() and upper_bound():

    • These algorithms require sorted sequences and random access. Priority queues are typically implemented using heap structures, and direct random access to elements is not provided. To find lower and upper bounds in the priority queue, you might need to reconsider the use of a sorted container or sort the priority queue before applying these operations.

  5. make_heap() and sort_heap():

    • These heap operations assume random access and efficient manipulation of elements, which is not directly applicable to priority queues. Priority queues are typically implemented using heap structures, and the heap operations are performed through enqueue and dequeue operations rather than direct access.

  6. merge():

    • Merging two sorted ranges efficiently requires random access, making it challenging with priority queues. If merging is a requirement, you might need to consider using other data structures or sort the priority queues before attempting to merge them.

  7. partition():

    • Partitioning elements based on a condition efficiently involves moving elements around, which is not directly supported by priority queues. If partitioning is necessary, you might need to use other data structures or reconsider the need for partitioning in the context of a priority queue.
0
Subscribe to my newsletter

Read articles from AL NAFIS FUAD SHUVO directly inside your inbox. Subscribe to the newsletter, and don't miss out.

#al_nafis_fuad_shuvoProgramming BlogsProgramming Tipsprogramming languagesProductivityprogrammeralgorithmscodingC++Databasesdata structuresCompetitive programmingComputer Science

Written by

AL NAFIS FUAD SHUVO
AL NAFIS FUAD SHUVO