你所不知道的数据结构——堆合集
cancan123456
·
·
个人记录
前排提示：本文包含二叉堆、多叉堆、配对堆、左偏树、斜堆、二项堆、lazy 二项堆、rank 配对堆、Fibonacci 堆、Brodal 队列、基数堆。
参考资料：
https://www.luogu.com.cn/blog/uakioi/radix-heaps-and-dij
首先扔复杂度：
| 操作 |
创建空堆 |
插入 |
查找最小值 |
删除最小值 |
合并 |
减小节点值 |
删除节点 |
均摊 or 最坏？ |
| 二叉堆 |
O(1) |
O(\log n) |
O(1) |
O(\log n) |
O(n) |
O(\log n) |
O(\log n) |
最坏 |
| m 叉堆 |
O(1) |
O(\log_mn) |
O(1) |
O(m\log_mn) |
O(n) |
O(\log_mn) |
O(m\log_mn) |
最坏 |
| 配对堆 |
O(1) |
O(1) |
O(1) |
O(\log n) |
O(1) |
下界 O(\log\log n)，上界 O(2^{2\sqrt{\log\log n}}) |
O(\log n) |
均摊 |
| 左偏树 |
O(1) |
O(\log n) |
O(1) |
O(\log n) |
O(\log n) |
O(\log n) |
O(\log n) |
最坏 |
| 斜堆 |
O(1) |
O(\log n) |
O(1) |
O(\log n) |
O(\log n) |
不适用 |
不适用 |
均摊 |
| 二项堆 |
O(1) |
O(\log n) |
O(\log n) |
O(\log n) |
O(\log n) |
O(\log n) |
O(\log n) |
最坏 |
| lazy 二项堆 |
O(1) |
O(1) |
O(1) |
O(\log n) |
O(\log n) |
O(\log n) |
O(\log n) |
均摊 |
| Fibonacci 堆 |
O(1) |
O(1) |
O(1) |
O(\log n) |
O(1) |
O(1) |
O(\log n) |
均摊 |
| rank 配对堆 |
O(1) |
O(1) |
O(1) |
O(\log n) |
O(1) |
O(1) |
O(\log n) |
均摊 |
| Brodal 队列 |
O(1) |
O(1) |
O(1) |
O(\log n) |
O(1) |
O(1) |
O(\log n) |
最坏 |
先提前说一下：除左偏树外，所有堆实现删除节点都是先减值为 -\infty 然后删除最小值，所以下面就不说了。
标题大小不太容易区分，为了避免没有层次我就扔云剪贴板了。
- 二叉堆 & 多叉堆
- 配对堆
- 左偏树
- 二项堆
- Fibonacci 堆
- rank 配对堆
- Brodal 队列
- [基数堆]