【模板】堆

题意

维护一个可重小根堆，支持插入、查询最小值和删除一个最小值。

思路

Python 标准库 heapq 在普通列表上实现小根堆：heappush 插入，heap[0] 查看堆顶，heappop 删除堆顶，正好对应三种操作。

Python 知识

heapq 原生是小根堆，重复值无需特殊处理。
百万次操作逐行读取，避免一次 split 的内存峰值。
查询结果追加到 bytearray，最后一次写出。

代码

C++ 用 priority_queue<ll, vector<ll>, greater<ll> > 就是标准库提供的小根堆：第三个模板参数 greater<ll> 把“数值小”当作“优先级高”，于是 push、top、pop 正好对应插入、查最小值和删除最小值三种操作，和上面 Python 的 heapq 一一对应，不必手写上浮下沉。堆内允许重复元素，top() 取到的始终是当前最小值，删除时也只弹出一个。

对应的 cppbook 章节：priority_queue：优先处理最重要的元素

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16import heapq
import sys


input = sys.stdin.buffer.readline
heap = []
output = bytearray()
for _ in range(int(input())):
    operation = input().split()
    if operation[0] == b"1":
        heapq.heappush(heap, int(operation[1]))
    elif operation[0] == b"2":
        output.extend(f"{heap[0]}\n".encode())
    else:
        heapq.heappop(heap)
sys.stdout.buffer.write(output)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 09:38
 * update_at: 2026-10-07 09:38
 */
// 【模板】堆：用 priority_queue 维护可重小根堆，push/top/pop 分别对应插入、查最小值、删除最小值。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

priority_queue<ll, vector<ll>, greater<ll> > pq; // 小根堆：堆顶始终是当前最小值，重复元素各占一个位置

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;

    // 依次处理 n 次操作：1 插入、2 输出最小值、3 删除最小值。
    for (ll i = 0; i < n; i++) {
        ll op;
        cin >> op;

        if (op == 1) {
            ll x;
            cin >> x;
            pq.push(x);
        } else if (op == 2) {
            cout << pq.top() << '\n';
        } else {
            pq.pop();
        }
    }

    return 0;
}

复杂度

插入、删除 $O(\log n)$ ，查看最小值 $O(1)$ ，空间 $O(n)$ 。

总结

Python OJ 的堆模板就是 heapq 三个基本接口，不必手写上浮下沉。

目录

题意

思路

Python 知识

代码

复杂度

总结