二维priority_queue

### 实现或使用二维优先队列 在 C++ 的标准模板库 (STL) 中，并不存在直接支持多维优先级队列的容器。然而，可以通过组合现有的 STL 容器和自定义比较函数来实现这一功能。通常情况下，二维优先队列是指基于两个维度进行排序的优先队列，比如 `(priority, value)` 对的形式。 #### 使用 `std::priority_queue` 和自定义比较函数 C++ 提供了 `std::priority_queue` 来处理单一维度的最大堆或最小堆需求。为了扩展到二维情况，可以将元素存储为一对值（如 `pair<int, int>` 或 `tuple<int, int>`），并通过提供自定义的比较逻辑来控制优先级顺序[^1]。 以下是具体实现： ```cpp #include <iostream> #include <queue> #include <vector> // 自定义比较函数类 struct Compare { bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) { if (a.first != b.first) { // 首先按第一个维度比较 return a.first > b.first; // 小顶堆 } return a.second > b.second; // 如果第一个维度相同，则按第二个维度比较 } }; int main() { // 创建一个二维优先队列 std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, Compare> pq; // 插入一些元素 pq.emplace(5, 3); pq.emplace(2, 8); pq.emplace(5, 7); pq.emplace(1, 9); // 输出队列中的元素 while (!pq.empty()) { auto [first, second] = pq.top(); std::cout << "(" << first << ", " << second << ")" << std::endl; pq.pop(); } return 0; } ``` 上述代码通过重载操作符的方式实现了二维优先队列的功能。其中，`Compare` 类用于指定优先级规则：首先按照第一个维度升序排列；如果第一个维度相等，则按照第二个维度升序排列。 #### 使用 `std::set` 或 `std::multiset` 另一种方法是利用有序集合 `std::set` 或允许重复键的 `std::multiset`。这些容器会自动根据其内部的比较函数保持有序状态。虽然它们不是严格意义上的优先队列，但在某些场景下也可以满足类似的用途[^2]。 示例代码如下： ```cpp #include <iostream> #include <set> int main() { // 使用 set 实现二维优先队列 std::set<std::pair<int, int>> s; // 插入一些元素 s.insert({5, 3}); s.insert({2, 8}); s.insert({5, 7}); s.insert({1, 9}); // 输出集合中的元素 for (auto it = s.begin(); it != s.end(); ++it) { std::cout << "(" << it->first << ", " << it->second << ")" << std::endl; } return 0; } ``` 此方法的优点在于能够轻松访问任意位置上的元素，而不仅仅是顶部元素。缺点则是不完全符合传统优先队列的操作模式。 #### 性能优化建议 当涉及大规模数据时，应特别注意底层数据结构的选择及其性能特性。例如，在实际应用中可能需要权衡插入效率与查询速度之间的关系。对于更复杂的场景，还可以探索其他高级数据结构或者并行计算技术以进一步提升算法表现[^3]。