堆(Heap)
堆是一种特殊类型的二叉树，堆具备两个性质：
- 每个结点的值大于（或小于）等于其每个子结点的值；
- 该二叉树是平衡二叉树。
如果根结点包含了最大的元素，则是大顶堆(max heap)；反之，是小顶堆（min heap）。
堆结构的最大好处是元素查找、插入和删除效率高($O(\log_2 n)$)。
堆按层的顺序存储在一个一维数组里$heap[SIZE]$。
如何根据结点序号求父结点序号？序号为$i(i>0)$的结点父结点序号是$i-1 \over 2$。
如何根据结点序号求子结点序号？序号为$i$（不是叶结点）的元素子结点序号是$2i+1$和$2i+2$。
堆的基本操作
堆的插入
以大顶堆为例：先将待新结点$e$放在堆的末尾，如果$e$不是根结点，并且比父结点的值大，就和父结点交换。
堆的删除
删除指删除堆顶元素。
以大顶堆为例：将最后一个叶结点中的元素放到要删除的元素位置（指堆顶），删除最后一个叶结点，将根元素$p$在不是叶结点的条件下，如果小于子结点，就和子结点的值交换，直到满足堆的条件。
堆的构造
堆有两种构造方法，分别是自顶向下和自底向上。
自顶向下构造法的原理是堆的插入算法；自底向上构造法的原理是从底层开始构造较小的堆，然后再重复构造较大的堆。
堆的应用
优先队列(Priority Queue)
与传统队列不同的是下一个服务对象是队列中优先级最高的元素。优先队列常用的实现方式是用堆，其最大好处是管理元素的效率高，时间复杂度是$O(\log_2 n)$。
堆排序
- 将原始序列转换为一个堆，称为原始堆，原始堆的根元素（序列的首元素）是最大元素。
- 将堆的首元素与当前堆的尾元素交换位置。（将当前最大元素放在当前序列的末端）
- 将“去掉”最大值元素后剩下的元素组成的子序列重新转换一个新的堆。
- 重复上述过程的第2至第3步n−1次。
堆排序的时间复杂度是$O(n\log_2 n)$，空间复杂度是$O(1)$（）无需额外辅助空间，堆排序是不稳定的。
二顶堆
斐波那契堆
两个堆还没细看，等二轮复习的时候来填坑。