跳转至

# 堆简介

堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值．

每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆．STL 中的 `priority_queue` 其实就是一个大根堆．

（小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值．

一些功能强大的堆（可并堆）还能（高效地）支持 merge 等操作．

一些功能更强大的堆还支持可持久化，也就是对任意历史版本进行查询或者操作，产生新的版本．

## 堆的分类

操作 `\` 数据结构1 | 配对堆 | 二叉堆 | 左偏树 | 二项堆 | 斐波那契堆
--- | --- | --- | --- | --- | ---
插入（insert） | 𝑂(1)O(1) | 𝑂(l o g⁡𝑛)O(log⁡n) | 𝑂(l o g⁡𝑛)O(log⁡n) | 𝑂(l o g⁡𝑛)O(log⁡n)2 | 𝑂(1)O(1)
查询最小值（find-min） | 𝑂(1)O(1) | 𝑂(1)O(1) | 𝑂(1)O(1) | 𝑂(1)O(1)34 | 𝑂(1)O(1)
删除最小值（delete-min） | 𝑂(l o g⁡𝑛)O(log⁡n)4 | 𝑂(l o g⁡𝑛)O(log⁡n) | 𝑂(l o g⁡𝑛)O(log⁡n) | 𝑂(l o g⁡𝑛)O(log⁡n) | 𝑂(l o g⁡𝑛)O(log⁡n)4
合并 (merge) | 𝑂(1)O(1) | 𝑂(𝑛)O(n) | 𝑂(l o g⁡𝑛)O(log⁡n) | 𝑂(l o g⁡𝑛)O(log⁡n) | 𝑂(1)O(1)
减小一个元素的值 (decrease-key) | 𝑜(l o g⁡𝑛)o(log⁡n)（下界 Ω(l o g⁡l o g⁡𝑛)Ω(log⁡log⁡n)，上界 𝑂(2 2√l o g⁡l o g⁡𝑛)O(2 2 log⁡log⁡n)）4 | 𝑂(l o g⁡𝑛)O(log⁡n) | 𝑂(l o g⁡𝑛)O(log⁡n) | 𝑂(l o g⁡𝑛)O(log⁡n) | 𝑂(1)O(1)4
是否支持可持久化 | ×× | ✓✓ | ✓✓ | ✓✓ | ××

习惯上，不加限定提到「堆」时往往都指二叉堆．

1. 表格来自于 Wikipedia ↩

2. 单次插入的复杂度为 𝑂(l o g⁡𝑛)O(log⁡n)，但有 𝑘 k 次连续插入时，可创建一个只包含要插入元素的二项堆，再将此堆与原先的二项堆进行合并，均摊复杂度为 𝑂(1)O(1) ↩

3. 可以保存一个指向最小元素的指针，在执行其他操作时修改该指针，即可在 𝑂(1)O(1) 的复杂度下进行查询了 ↩

4. 复杂度为均摊复杂度 ↩↩↩↩↩

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：HeRaNO, CCXXXI, CyaceQuious, Enter-tainer, Ir1d, Tiphereth-A, WAAutoMaton, Early0v0, mgt, ouuan, shuzhouliu, sshwy
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用