C++ 优先级队列

一、引言

• 队列的特性是先进先出。
• 优先级队列的本质是一个有序队列，根据成员的优先级，对队列中的成员进行排序。
• 优先级队列默认是大顶堆，即堆顶元素最大

二、常用函数

• empty()
• size()
• top()
• push()
• emplace()
• pop()
• swap()

三、代码示例

class SS {
 public:
  SS(int _val = 0) : val(_val) {}
  bool operator<(const SS& ss) const { return val < ss.val; } // 声明 pq1 的基础
  bool operator>(const SS& ss) const { return val > ss.val; } // 声明 pq2 的基础
  int val;
};

struct SS_Compare {
 public:
  bool operator()(const SS& ss1, const SS& ss2) const { // 声明 pq 的基础
    return ss1.val < ss2.val;
  }
};

int main() {
  priority_queue<SS, vector<SS>, SS_Compare> pq;
  priority_queue<SS, vector<SS>, less<SS>> pq1;
  priority_queue<SS, vector<SS>, greater<SS>> pq2;
  pq.push(SS(1));
  pq.push(SS(2));
  pq.push(SS(3));

  vector<SS> v;
  sort(v.begin(), v.end(), SS_Compare());

  while (!pq.empty()) {
    std::cout << pq.top().val << std::endl;
    pq.pop();
  }

  return 0;
}

四、自定义排序方法

在上述的代码示例中，展示了三种使用自定义排序函数的方法：

• 使用仿函数
• 重载<，然后使用less
• 重载>，然后使用greater

注意到，在使用仿函数的时候，我们给优先级队列传递的是类型，而在sort()函数中使用仿函数的时候，我们传递的实参是临时函数对象。
这个差异源于优先级队列(priority_queue)和排序算法(sort)在C++中不同的设计方式。
那为什么要这么设计呢？？？

1. 优先级队列: 需要存储比较器作为成员变量，因此需要在构造时知道类型
2. 排序算法: 是一次性操作，可以直接接受一个比较器对象
   这种设计差异是C++标准库的历史和实用性的结果，反映了不同容器和算法的使用模式。

五、容器

优先级队列使用的默认容器是vector，也可以选用deque或者自定义容器类型。
但自定义容器类型必须满足一些要求才能被优先级队列接受。
此外，默认容器vector已经足够高效，所以通常不建议使用自定义容器。