题解 | #【模板】整数优先队列#

题目链接

【模板】整数优先队列

题目描述

你需要实现一个支持以下三种操作的整数多重集合（允许存在重复元素）：

插入 x: 1 x，将一个整数 x 加入集合。
查询最小: 2，输出集合中的最小元素。
删除最小: 3，删除集合中的一个最小元素。

这是一个主函数模式的题目，你需要自己处理输入和输出。

输入格式:

第一行是一个整数 $N$ ，表示操作的总数。
接下来 $N$ 行，每行描述一个操作。

输出格式:

对于每个查询操作（类型 2），输出一行，内容为当前集合中的最小元素。

示例: 输入:

输出:

3
3
5

解题思路

这个问题要求我们动态地维护一个集合，并能高效地进行插入、查询最小值和删除最小值这三种操作。这正是优先队列（Priority Queue），特别是**最小堆（Min-Heap）**的经典应用场景。

为什么使用最小堆？ 最小堆是一种特殊的树形数据结构，它能保证其根节点始终是整个集合中的最小元素。这使得它能以非常高的效率支持我们需要的操作：
- 插入 (Insert): 将新元素加入堆并调整，时间复杂度为 $\mathcal{O}(\log N)$ 。
- 查询最小值 (Find-Min): 直接返回根节点的值，时间复杂度为 $\mathcal{O}(1)$ 。
- 删除最小值 (Delete-Min): 移除根节点并重新调整堆，时间复杂度为 $\mathcal{O}(\log N)$ 。

这比使用普通数组或列表（查询和删除慢）或已排序数组（插入慢）要高效得多。

各语言实现

C++: 使用标准库中的 std::priority_queue。默认情况下，它是一个最大堆。要实现最小堆，我们需要提供一个不同的比较器，即 std::greater<int>。
Java: 使用 java.util.PriorityQueue 类。它在默认情况下就是一个最小堆，直接使用即可。
Python: 使用 heapq 模块。这个模块提供了一系列函数，可以将一个普通的列表 list 当作最小堆来操作。

算法步骤:

初始化一个空的优先队列（最小堆）。
循环 $N$ 次，读取每个操作。
根据操作类型执行相应操作：
- op == 1: 读取整数 x，将其插入优先队列。
- op == 2: 访问并输出优先队列的队首元素（即最小值）。
- op == 3: 从优先队列中移除队首元素。
在进行查询或删除前，最好检查队列是否为空，以避免运行时错误（尽管本题数据可能保证了操作的合法性）。

代码

cpp
java
python

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

using namespace std;

int main() {
    int n;
    cin >> n;
    // 默认是最大堆，需要用 greater<int> 转换为最小堆
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for (int i = 0; i < n; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            pq.push(x);
        } else if (op == 2) {
            if (!pq.empty()) {
                cout << pq.top() << "\n";
            }
        } else if (op == 3) {
            if (!pq.empty()) {
                pq.pop();
            }
        }
    }
    
    return 0;
}

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // Java的PriorityQueue默认是最小堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int i = 0; i < n; i++) {
            int op = sc.nextInt();
            switch (op) {
                case 1:
                    int x = sc.nextInt();
                    pq.add(x);
                    break;
                case 2:
                    if (!pq.isEmpty()) {
                        System.out.println(pq.peek());
                    }
                    break;
                case 3:
                    if (!pq.isEmpty()) {
                        pq.poll();
                    }
                    break;
            }
        }
    }
}

import heapq

def main():
    n = int(input())
    # Python的heapq模块直接在列表上操作，实现最小堆
    min_heap = []
    
    for _ in range(n):
        parts = list(map(int, input().split()))
        op = parts[0]
        
        if op == 1:
            x = parts[1]
            heapq.heappush(min_heap, x)
        elif op == 2:
            if min_heap:
                print(min_heap[0])
        elif op == 3:
            if min_heap:
                heapq.heappop(min_heap)

if __name__ == "__main__":
    main()

算法及复杂度

数据结构: 优先队列（最小堆）
时间复杂度: 对于 $N$ 次操作，其中插入和删除的代价是 $\mathcal{O}(\log k)$ ，查询是 $\mathcal{O}(1)$ （其中 $k$ 是堆中当前的元素数量）。如果总共有 $N$ 次操作，堆中最多有 $N$ 个元素，总时间复杂度为 $\mathcal{O}(N \log N)$ 。
空间复杂度: $\mathcal{O}(N)$ ，在最坏的情况下，所有操作都是插入操作，需要存储 $N$ 个整数。