堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。
每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。
堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。
一些功能强大的堆（可并堆）还能（高效地）支持 merge 等操作。
二叉树
满二叉树
国内定义
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。
满二叉树满足如下性质：
1、一个层数为k 的满二叉树总结点数为：(2^k)-1。因此满二叉树的结点树一定是奇数个。
2、第i层上的结点数为：2^(i-1)
3、一个层数为k的满二叉树的叶子结点个数（也就是最后一层）：2^(k-1)
国际定义
二叉树的结点要么是叶子结点，要么它有两个孩子结点。
完全二叉树
允许最后一层有空缺结点且空缺在右边
堆分类
配对堆 二叉堆 左偏树 二项堆 斐波那契堆
大根堆
小根堆
二叉堆
堆是一种完全二叉树
对于任意一个父节点的序号n来说（这里n从0算），它的子节点的序号一定是2n+1,2n+2
左偏树
操作
以大根堆为例
插入(insert)
插入操作是指向二叉堆中插入一个元素，要保证插入后也是一棵完全二叉树。
在最下一层最右边的叶子之后插入,如果最下一层已满，就新增一层。
向上调整
如果这个结点的权值大于它父亲的权值，就交换，重复此过程直到不满足或者到根。 O(log n)
查询最小值(find-mid)
删除(delete)
删除操作指删除堆中最大的元素，即删除根结点.
设法将根结点移到最后一个结点，然后直接删掉
方法：把根结点和最后一个结点直接交换，
于是直接删掉（在最后一个结点处的）根结点。
向下调整
在该结点的儿子中，找一个最大的，与该结点交换，重复此过程直到底层。 O(log n)
增加某个点的权值
直接修改后，向上调整一次 O(log n)
合并(merge)
减小一个元素的值(decrease-key)
优先队列
STL库里的堆
empty() 队列为空返回真
pop() 删除队顶元素
push() 加入一个元素
size() 返回优先队列中拥有的元素个数
top() 返回优先队列对顶元素
默认的优先队列是大根堆,复杂度跟堆一样.
自动维护一个最值
转换大小根堆
1 | //转为大根堆 |