C++ 第44题：std::priority_queue 优先队列：默认大顶堆与 std::greater 小顶堆构建

题目

编写程序，演示优先队列 std::priority_queue 的底层堆结构（二叉堆 Binary Heap）。展示其默认以 std::less 构建的大顶堆（Max-Heap，堆顶为最大值）；并通过显式传入底层容器与比较器 std::priority_queue<int, std::vector<int>, std::greater<int>> 构建小顶堆（Min-Heap，堆顶为最小值），分析其 push 与 pop 的 O(log N) 堆调整机制。

输入格式：无需外部输入。

输出格式：分别按从大到小与从小到大的顺序弹出并打印堆内元素。

数据范围与约定：二叉堆性质与比较器方向辨析。

思路与算法

1. 比较器方向的反直觉特性
初学者常误以为 std::greater 构建大顶堆。STL 优先队列的规则是：当比较器 Comp(a, b) 为真时，b 的优先级高于 a（即 a 要下沉）。因此 std::less 使得较大值位于堆顶（大顶堆），而 std::greater 使得较小值位于堆顶（小顶堆）。

2. 只读堆顶 top
优先队列不支持像普通 queue 那样的 front()，也不支持任意迭代器遍历。它仅暴露 top() 访问堆顶，以及 pop() 弹出堆顶。

3. 底层支持容器
priority_queue 的底层容器通常为 std::vector 或 std::deque，依托标准算法 std::push_heap 与 std::pop_heap 维护堆序性。

完整程序

#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::vector<int> numbers = {45, 12, 89, 34, 7, 63, 12};

    // 1. 默认大顶堆（Max-Heap，顶部永远是最大值）
    std::priority_queue<int> maxHeap;
    for (int x : numbers) {
        maxHeap.push(x);
    }

    std::cout << "--- 1. 大顶堆弹出顺序 (降序) ---\n";
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " ";
        maxHeap.pop(); // O(log N) 调整堆
    }
    std::cout << "\n\n";

    // 2. 小顶堆（Min-Heap，顶部永远是最小值）
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    for (int x : numbers) {
        minHeap.push(x);
    }

    std::cout << "--- 2. 小顶堆弹出顺序 (升序) ---\n";
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }
    std::cout << "\n";

    return 0;
}

运行示例

输出：

--- 1. 大顶堆弹出顺序 (降序) ---
89 63 45 34 12 12 7 

--- 2. 小顶堆弹出顺序 (升序) ---
7 12 12 34 45 63 89