【模板】堆

GitHub跳转原题关系图返回列表

用 heapq 直接维护可重复整数小根堆，并用 bytearray 批量输出。

OJ: luogu

题目 ID: P3378

难度:普及-

标签:二叉堆heapq模板题python

日期: 2026-07-16 21:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

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

思路

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

Python 知识

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

代码

python
import 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)

复杂度

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

总结

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