堆简介¶
堆是一种数据结构，维护一个数的集合（或者，一个支持比较的元素的集合）。
主要功能有：insert, getmin, deletemin, decreasekey。
注意：简单起见，我们这里讨论的都是维护最小值的堆，也叫小根堆，与之相对的叫做大根堆。
一些功能强大的堆还能（高效地）支持 merge 等操作。
一些功能更强大的堆还支持可持久化，也就是对任意历史版本进行查询或者操作，产生新的版本。
堆的分类¶
| 操作\数据结构 | 配对堆 | 二叉堆 | 左偏树 | 二项堆 | 斐波那契堆 |
|---|---|---|---|---|---|
| 插入（insert） | |||||
| 查询最小值（find-min） | |||||
| 删除最小值（delete-min） | |||||
| 合并 (merge) | |||||
| 减小一个元素的值 (decrease-key) | |||||
| 是否支持可持久化 |
一个有趣的事实是，这些堆都是用基于树的数据结构实现的。
在 OI 中，最常用的堆是二叉堆，习惯上不加限定提到“堆”时往往也指二叉堆。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用