priority_queue pair 小堆顶怎么实现
时间: 2023-08-08 21:10:52 浏览: 70
要实现一个小堆顶的 priority_queue,你可以使用 C++ 中的 STL 库中的 priority_queue,并自定义一个比较函数来实现。在比较函数中,将要比较的 pair 的第一个元素作为主要比较依据,如果第一个元素相等,则比较第二个元素。
下面是一个示例代码:
```cpp
#include <iostream>
#include <queue>
using namespace std;
struct Compare {
bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) {
if (p1.first == p2.first) {
return p1.second > p2.second;
}
return p1.first > p2.first;
}
};
int main() {
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
pq.push(make_pair(1, 5));
pq.push(make_pair(2, 3));
pq.push(make_pair(3, 1));
while (!pq.empty()) {
pair<int, int> topPair = pq.top();
cout << topPair.first << ", " << topPair.second << endl;
pq.pop();
}
return 0;
}
```
在上述示例中,我们定义了一个名为 `Compare` 的结构体,重载了 `()` 运算符作为比较函数。然后,我们使用 `priority_queue` 容器,并将 `Compare` 结构体作为第三个模板参数传递给它。这样,我们就可以使用小堆顶的 `priority_queue<pair<int, int>>` 了。
希望能帮到你!如有任何问题,请随时提问。