其他数据结构

stack (栈): push(), pop(), top(), ...
queue (队列): push(), pop(), front(), back(), ...
deque (双端队列): push_back(), push_front(), 支持迭代器, ...
priority_queue (优先队列): 带有优先级的队列（默认：降序排列，即最大值优先，不是升序）

priority_queue<int> pq;
int zahlen[] = {1, 7, 8, 3, 12, 6, 5, 2};
for (int i: zahlen) 
    pq.push(i);

while (!pq.empty()){
    cout << pq.top() << " "; // 输出堆顶（当前最大值）
    pq.pop();                // 移除堆顶元素
}
cout << endl;

输出:

12 8 7 6 5 3 2 1

一个非常经典的应用：使用对顶堆（一个大根堆和一个小根堆）来动态地求解第K大（或第K小）的数。

问题场景

假设我们有一个数据流，需要在任意时刻都能快速查询当前所有已读入数字中的第K大的数。

核心思想：对顶堆

使用两个优先队列 (priority_queue)： 大根堆 (max_heap): 用于存储所有数字中较小的那部分。堆顶是这部分中的最大值。 小根堆 (min_heap): 用于存储所有数字中较大的那部分。堆顶是这部分中的最小值。

关键维护条件：让小根堆的大小恰好等于 K。

这意味着小根堆里存放的是当前所有数字中最大的K个数。 因此，小根堆的堆顶就是这K个数中最小的，也就是第K大的数。

算法步骤 (求第K大)

初始化: 创建一个大根堆 max_heap (在C++中通过 priority_queue<int> 实现)。 创建一个小根堆 min_heap (在C++中通过 priority_queue<int, vector<int>, greater<int> >实现)。 设定目标 K。 处理每个新数字 num:

情况1: 如果 min_heap 的大小小于 K。

直接将 num 加入 min_heap。 (因为还没满K个，先放进去)

情况2: 如果 min_heap 的大小等于 K。

比较 num 和 min_heap 的堆顶 min_heap.top()。

如果 num > min_heap.top():

说明 num 比当前第K大的数还大，它有资格进入“最大的K个数”这个集合。 将 min_heap 的堆顶（即当前的第K大）弹出并加入 max_heap。 将新的 num 加入 min_heap。 (这样 min_heap 仍然是K个最大的数，且第K大被更新)

如果 num <= min_heap.top():

说明 num 不够大，进不了“最大的K个数”集合。 直接将 num 加入 max_heap。

查询第K大:

只要 min_heap 的大小等于 K，min_heap.top() 就是当前的第K大数。 如果总数字少于 K，则第K大不存在。

C++ 代码示例

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 全局变量
priority_queue<int> max_heap; // 大根堆，存储较小的部分
priority_queue<int, vector<int>, greater<int>> min_heap; // 小根堆，存储最大的K个数
int K; // 目标：求第K大

// 添加一个数字到数据流
void addNumber(int num) {
    if (min_heap.size() < K) {
        min_heap.push(num);
    } else {
        if (num > min_heap.top()) {
            max_heap.push(min_heap.top());
            min_heap.pop();
            min_heap.push(num);
        } else {
            max_heap.push(num);
        }
    }
}

// 获取当前第K大的数
int getKthLargest() {
    return min_heap.size() == K ? min_heap.top() : -1; // 简化返回，ACM中通常保证数据足够
}

int main() {
    // 输入K
    cin >> K;

    // 模拟数据流，这里用vector代替，ACM中可能是while循环读入
    vector<int> stream = {4, 5, 8, 2, 3, 9, 7};

    cout << "Processing stream: ";
    for (int num : stream) {
        cout << num << " ";
        addNumber(num);
        int kth = getKthLargest();
        if (kth != -1) {
            cout << "(Kth largest now: " << kth << ") ";
        }
    }
    cout << endl;

    cout << "The " << K << "rd largest number is: " << getKthLargest() << endl;

    return 0;
}

输出示例

Processing stream: 4 5 8 (Kth largest now: 4) 2 3 (Kth largest now: 4) 9 (Kth largest now: 5) 7 (Kth largest now: 7) 
The 3rd largest number is: 7

解释 加入 4, 5, 8 后，min_heap 有 {4, 5, 8} (内部是小根堆，堆顶4)，第3大是 4。 加入 2, 3 后，它们小于4，进入 max_heap。min_heap 不变，第3大仍是 4。 加入 9，9 > 4，所以4被弹出到 max_heap，9进入 min_heap。现在 min_heap 有 {5, 8, 9}，堆顶是5，第3大变为 5。 加入 7，7 > 5，所以5被弹出到 max_heap，7进入 min_heap。现在 min_heap 有 {7, 8, 9}，堆顶是7，第3大变为 7。 这种方法的时间复杂度是 O(log K) 插入和 O(1) 查询，非常高效。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com