跳转至

堆简介

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

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

(小根)堆主要支持的操作有:插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。

一些功能强大的堆(可并堆)还能(高效地)支持 merge 等操作。

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

堆的分类

操作 \ 数据结构1配对堆二叉堆左偏树二项堆斐波那契堆
插入(insert)O(1)O(logn)O(logn)O(logn)2O(1)
查询最小值(find-min)O(1)O(1)O(1)O(1)34O(1)
删除最小值(delete-min)O(logn)4O(logn)O(logn)O(logn)O(logn)4
合并 (merge)O(1)O(n)O(logn)O(logn)O(1)
减小一个元素的值 (decrease-key)o(logn)(下界 Ω(loglogn),上界 O(22loglogn)4O(logn)O(logn)O(logn)O(1)4
是否支持可持久化××

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


  1. 表格来自于 Wikipedia 

  2. 单次插入的复杂度为 O(logn),但有 k 次连续插入时,可创建一个只包含要插入元素的二项堆,再将此堆与原先的二项堆进行合并,均摊复杂度为 O(1) 

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

  4. 复杂度为均摊复杂度