特点
堆是一种特殊树
前提条件
堆是一个完全二叉树
完全二叉树: 除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列
堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值
堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值
名词解释
大顶堆: 对于每个节点的值都大于等于子树中每个节点值的堆
小顶堆: 对于每个节点的值都小于等于子树中每个节点值的堆
其中图1和图2为大顶堆，图3为小顶堆，图4不是堆
具体实现
完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间
数组中，左子节点是下标为i*2，右子节点是下标为i*2+1，父节点是下标为\frac{i}{2}
大顶堆插入一个元素
往堆中插入一个元素后，需要继续满足堆的两个特性，不满足则需要进行堆化操作
堆化: 顺着节点所在的路径，向上或者向下，对比然后交换
用新插入的节点与父节点对比大小，不满足子节点小于等于父节点大小关系则互换节点
一直重复上述过程，直到父子节点之间满足以上大小关系
大顶堆删除堆顶元素
堆顶元素存储的就是堆中数据的最大值或者最小值
假设我们构造的是大顶堆，堆顶元素就是最大的元素。当我们删除堆顶元素之后，就需要把第二大的元素放到堆顶，那第二大元素肯定会出现在左右子节点中。然后我们再迭代地删除第二大节点，以此类推，直到叶子节点被删除
最后从下往上堆化出来的堆并不满足完全二叉树的特性
最后从上往下堆化出来的堆满足完全二叉树的特性
移除的是数组中的最后一个元素，在堆化的过程中是交换操作，不会出现数组中的“空洞”
时间复杂度
一个包含n个节点的完全二叉树，树的高度不会超过logn
堆化的过程是顺着节点所在路径比较交换，堆化时间复杂度跟树的高度成正比为O(logn)
插入数据和删除堆顶元素的主要逻辑就是堆化，所以时间复杂度为O(logn)
基于堆实现排序
特点
时间复杂度非常稳定为O(n*logn)
原地排序算法
堆排序过程
1.建堆: 将数组原地(不借助另一个数组，就在原数组上操作)建成一个堆
具体过两次
1.从前往后处理数组数据，并且每个数据插入堆中时都是从下往上堆化
数组包含n个数据，假设起初堆中只包含一个数据，就是下标为1的数据，
调用前面讲的插入操作，将下标从2到n的数据依次插入到堆中，
这样将包含n个数据的数组组织成了堆
2.从后往前处理数组，并且每个数据插入堆中时都是从上往下堆化
从上往下堆化代码实现
private static void buildHeap(int[] a, int n) {
for (int i = n/2; i >= 1; --i) {
heapify(a, n, i);
}
}
private static void heapify(int[] a, int n, int i) {
while (true) {
int maxPos = i;
if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
if (maxPos == i) break;
swap(a, i, maxPos);
i = maxPos;
}
}
下标从开始到1的数据进行堆化，下标从
+1到n的节点不需要堆化
对于完全二叉树来说，下标从+1到n的节点都是叶子节点
建堆操作的时间复杂度
单节点堆化时间复杂度为O(log n)，+1个节点堆化的总时间复杂度是O(nlog n)?
这个答案不够精确。实际上堆排序的建堆过程的时间复杂度是O(n)
推导公式如下
因为叶子节点不需要堆化，所以需要堆化的节点从倒数第二层开始。
每个节点堆化的过程中，需要比较和交换的节点个数，跟这个节点的高度k成正比
只需要将每个节点的高度求和即总时间复杂度
将每个非叶子节点的高度求和，就是下面这个公式
S中间部分是一个等比数列，最后用等比数列的求和公式来计算，最终的结果如下图
因为h=，代入公式S就能得到S=O(n)，所以建堆的时间复杂度就是O(n)
2.排序
建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的
排序过程--类似于删除堆顶元素顶过程
大顶堆第一个元素是最大元素，它跟最后一个元素交换后最大元素放到下标n的位置
当堆顶元素移除之后，我们把下标为n的元素放到堆顶，
然后再通过堆化的方法，将剩下的n-1个元素重新构建成堆
堆化完成之后，我们再取堆顶的元素，放到下标是n-1的位置，
一直重复这个过程，直到最后堆中只剩下标为1的一个元素，排序工作就完成了
// n表示数据的个数，数组a中的数据从下标1到n的位置
public static void sort(int[] a, int n) {
buildHeap(a, n);
int k = n;
while (k > 1) {
swap(a, 1, k);
--k;
heapify(a, k, 1);
}
}
原地排序算法
整个堆排序的过程，都只需要极个别临时存储空间
时间复杂度
堆排序包括建堆和排序两个操作，整体的时间复杂度是O(nlogn)
建堆过程的时间复杂度是O(n)，排序过程的时间复杂度是O(nlogn)
不稳定排序算法
排序过程存在将堆最后节点跟堆顶节点互换操作，有可能改变值相同数据的原始顺序
为什么快速排序要比堆排序性能好
第一点，堆排序数据访问的方式没有快速排序友好
快速排序数据是顺序访问的，对CPU缓存友好
堆排序数据是跳着访问的，对CPU缓存不友好
第二点，对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序
排序两个概念: 有序度和逆序度
对于基于比较的排序算法，整个排序过程只有由比较和交换/移动两个操作组成
快速排序数据交换的次数不会比逆序度多
堆排序的第一步是建堆，建堆过程会打乱数据原有相对先后顺序，导致原数据有序度降低
堆排序比快速排序交换次数多
应用场景
1.优先级队列
优先级队列中，数据的出队顺序不是先进先出，而是按照优先级最高的最先出队
如何实现一个优先级队列
方法有很多，但是用堆来实现是最直接、最高效的。堆和优先级队列非常相似
往优先级队列中插入一个元素，就相当于往堆中插入一个元素；
从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素
以下算法依赖优先级队列
赫夫曼编码、图的最短路径、最小生成树算法等等
优先级队列的语言实现
Java的PriorityQueue，C++的priority_queue等
2.利用堆求Top K--如何在一个包含n个数据的数组中，查找前K大数据
可以维护一个大小为K小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。
如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；
如果比堆顶元素小，则不做处理，继续遍历数组。
这样等数组中的数据都遍历完之后，堆中的数据就是前K大数据了
遍历数组需要O(n)的时间复杂度，一次堆化操作需要O(logK)的时间复杂度
最坏情况下，n个元素都入堆一次，所以时间复杂度就是O(nlogK)
3.利用堆求中位数
需要维护两个堆，一个大顶堆，一个小顶堆
大顶堆存储前半部分数据，小顶堆存储后半部分数据，且小顶堆数据都大于大顶堆数据
如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；
如果新加入的数据大于等于小顶堆的堆顶元素，我们就将这个新数据插入到小顶堆
插入数据需要堆化时间复杂度为O(logn)，求中位数即大顶堆堆顶元素时间复杂度为O(1)
