WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆简介
二叉堆
配对堆
左偏树
分块思想
块状数组
块状链表
树分块
Sqrt Tree
单调栈
单调队列
ST 表
树状数组
线段树
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树简介
Treap
Splay
WBLT
Size Balanced Tree
AVL 树
替罪羊树
笛卡尔树
左偏红黑树
跳表
可持久化数据结构简介
可持久化线段树
可持久化块状数组
可持久化平衡树
可持久化字典树
可持久化可并堆
线段树套线段树
平衡树套线段树
线段树套平衡树
树状数组套主席树
分块套树状数组
K-D Tree
珂朵莉树
Link Cut Tree
Euler Tour Tree
Top Tree
析合树
50 objects
本站非官方,所收集资源均来源于网络。
堆简介 - 数据结构
author: ouuan 堆是一棵树,其每个节点都有一个键值,且每个节点的键值都大于等于/小于等于其父亲的键值。 每个节点的键值都大于等于其父亲键值的堆叫做小根堆,否则叫做大根堆。STL 中的 `priority_queue` 其实就是一个大根堆。 (小根)堆主要支持的操作有:插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。 一些功能强大的堆(可并堆)还能(高效地)支持 merge 等操作。 一些功能更强大的堆还支持可持久化,也就是对任意历史版本进行查询或者操作,产生新的版本。 ## 堆的分类 | 操作\\\\数据结构 | 配对堆 | 二叉堆 | 左偏树 | 二项堆 | 斐波那契堆 | | :---------------------: | :-----------------------------------------------------------------------: | :------------: | :------------: | :------------: | :-----------: | | 插入(insert) | $O(1)$ | $O(\log n)$ | $O(\log n)$ | $O(1)$ | $O(1)$ | | 查询最小值(find-min) | $O(1)$ | $O(1)$ | $O(1)$ | $O(\log n)$ | $O(1)$ | | 删除最小值(delete-min) | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | | 合并 (merge) | $O(1)$ | $O(n)$ | $O(\log n)$ | $O(\log n)$ | $O(1)$ | | 减小一个元素的值 (decrease-key) | $o(\log n)$ (下界 $\Omega(\log \log n)$ ,上界 $O(2^{2\sqrt{\log \log n}})$ ) | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(1)$ | | 是否支持可持久化 | $\times$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\times$ | 习惯上,不加限定提到“堆”时往往都指二叉堆。