优先队列

06 Oct 2024

1. 简介

优先队列（priority_queue）是一种“每次都能快速取出当前最优元素”的数据结构。普通队列按照进入顺序取出元素，而优先队列会按照元素的优先级取出。

在 C++ 中，优先队列通常由堆实现：

默认是大根堆，每次取出当前最大的元素。
使用 greater<int> 可以得到小根堆，每次取出当前最小的元素。

它适合“反复加入元素，并反复选出当前最大或最小元素”的问题。

2. 基本用法

#include <bits/stdc++.h>
using namespace std;

priority_queue<int> maxHeap; // 大根堆：top() 是最大值
priority_queue<int, vector<int>, greater<int> > minHeap; // 小根堆：top() 是最小值

常用操作如下：

q.push(x)  // 插入 x
q.top()    // 查看堆顶元素，不删除
q.pop()    // 删除堆顶元素
q.empty()  // 判断队列是否为空
q.size()   // 当前元素数量

插入和删除堆顶的时间复杂度都是 O(log n)，查看堆顶是 O(1)。因此，不需要每次排序整个数组，也能持续得到当前最小值或最大值。

3. 例题

示例：洛谷 P3378 【模板】堆

这是一道优先队列的基础模板题，包含三种操作：插入一个数、输出当前最小值、删除当前最小值。

题目要求的正是小根堆最基本的 push、top 和 pop 操作。使用 greater<int> 建立小根堆后，堆顶始终是当前所有元素中的最小值。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    priority_queue<int, vector<int>, greater<int> > q;
    while (n--) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;
            q.push(x);
        } else if (op == 2) {
            cout << q.top() << '\n';
        } else {
            q.pop();
        }
    }
    return 0;
}

优先队列的核心不是“把所有数据完全排好序”，而是始终维护当前最需要的那个元素。当题目反复要求最大值、最小值或当前最优选择时，优先队列通常是一个直接而高效的工具。

优先队列

Related Posts