部分内容来自 OI-WIKI。
1. 堆
- 堆的定义
堆是一棵二叉树，满足每个节点的键值都大于等于它的父亲节点或者小于等于它的父亲节点。每个节点的键值都大于等于它的父亲节点的叫小根堆，每个节点的键值都小于等于它的父亲节点的叫大根堆。
优先队列是一种抽象数据类型，它是一种容器，里面有一些元素，这些元素也称为队列中的节点。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点，取得最小/大节点和删除最小/大节点。
常见的优先队列是二叉堆。
可并堆代表一种抽象数据结构，不仅能支持以上三种操作，还支持将两个堆合为一个的操作。但是两个二叉堆合并的时间复杂度是 \(O(n)\) 的，十分不优秀。所以存在配对堆、二项堆、左偏树等可以在 \(O(\log n)\) 甚至 \(O(1)\) 的时间复杂度内进行堆的合并。
单次操作时间复杂度：
- 二叉堆
- 配对堆
- 左偏树
2. 二叉搜索树
- 二叉搜索树的定义
- 笛卡尔树
- 旋转 Treap
- FHQ Treap
- Splay