C++ Priority Queue Implementation Guide

In C++, you can use std::priority_queue to implement a priority queue. std::priority_queue is a template class located in the header file.

Before using std::priority_queue, it is necessary to define the type of elements and the way in which elements will be compared. The comparison can be achieved by defining a function object or using a Lambda expression.

Here is an example of implementing a priority queue using std::priority_queue:

#include <iostream>
#include <queue>

int main() {
  // 定义元素类型为整数，比较方式为从大到小
  std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

  // 插入元素
  pq.push(3);
  pq.push(1);
  pq.push(4);
  pq.push(1);
  pq.push(5);

  // 输出队列中的元素
  while (!pq.empty()) {
    std::cout << pq.top() << " ";
    pq.pop();
  }

  return 0;
}

The output result is: 1 1 3 4 5

In the example above, we defined a priority queue named pq with integer elements sorted from highest to lowest priority. By using the push function, we inserted elements into the queue, the top function to retrieve the element with the highest priority, and the pop function to remove the element with the highest priority. Finally, we looped through the queue to output its elements.

It is important to note that by default, std::priority_queue uses std::less as the comparison method, meaning it orders items in descending order. If you need items to be ordered in ascending order, you can use std::greater as the comparison method.