priority_queue<int, vector<int>, greater<int>>

优先队列（`priority_queue`）是 C++ STL 中的一个容器适配器，它提供了一种基于堆结构的数据访问方式。默认情况下，`priority_queue` 是一个最大堆，即堆顶元素为最大的元素。如果希望实现一个最小堆，则需要对默认的比较函数进行调整。 ### 最小堆的声明 在 C++ STL 中，可以通过以下方式声明一个最小堆： ```cpp std::priority_queue<int, std::vector<int>, std::greater<int>> pq; ``` 其中： - 第一个模板参数 `int` 表示存储的元素类型。 - 第二个模板参数 `std::vector<int>` 表示底层容器类型，通常使用 `std::vector`。 - 第三个模板参数 `std::greater<int>` 表示比较函数对象类型，用于构建最小堆[^1]。 ### 基本用法 可以使用 `push()` 方法将元素插入堆中，使用 `top()` 方法获取堆顶元素（即当前最小值），并使用 `pop()` 方法移除堆顶元素。以下是一个完整的示例程序： ```cpp #include <iostream> #include <queue> int main() { // 声明一个最小堆 std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // 插入元素 pq.push(10); pq.push(30); pq.push(20); pq.push(5); pq.push(1); // 输出并移除堆中的元素 while (!pq.empty()) { std::cout << "Top element: " << pq.top() << std::endl; pq.pop(); } return 0; } ``` 该程序会按照从小到大的顺序输出堆中的元素，因为最小堆始终将当前最小值放在堆顶位置[^2]。 ### 复杂数据类型的最小堆 当使用复杂数据类型（如 `std::pair` 或自定义结构体）时，可以通过指定比较函数来控制排序规则。例如，对于 `std::pair<int, int>` 类型，默认情况下，`std::greater<std::pair<int, int>>` 会根据 `first` 成员进行排序： ```cpp #include <iostream> #include <queue> #include <utility> int main() { // 声明一个存储 pair 的最小堆 std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq; // 插入元素 pq.emplace(10, 2); pq.emplace(9, 4); pq.emplace(8, 6); pq.emplace(7, 8); pq.emplace(6, 10); pq.emplace(5, 9); pq.emplace(4, 7); pq.emplace(3, 5); pq.emplace(2, 3); pq.emplace(1, 1); // 输出并移除堆中的元素 while (!pq.empty()) { std::cout << pq.top().first << " " << pq.top().second << std::endl; pq.pop(); } return 0; } ``` 此代码片段展示了如何构建一个以 `pair<int, int>` 为元素类型的最小堆，并按照 `first` 成员进行排序输出[^3]。 ---