数据结构与算法(三)——堆及其应用
一、什么是堆？
作为一种数据结构，堆是一个完全二叉树，且堆中每个节点的值必须大于等于(或小于等于)其子节点的值。
- 对于每个节点的值都大于等于其子节点值的堆，称作“大顶堆”。
- 对于每个节点的值都小于等于其子节点值的堆，称作“小顶堆”。
下图为大顶堆。
二、堆的存储方式
堆作为一种完全二叉树，比较适合用数组来存储，这样就不用像二叉树一样，每个节点都要存储左右子节点的指针了。用数组存储只需要通过数组下标，就可以找到当前节点的左右子节点。
如图，数组下标为i的节点，其左子节点的下标为2 * i，右子节点的下标为2 * i + 1，父节点的坐标为 i / 2。
三、堆的基本操作
1、堆的插入
先将需要新节点，以满足完全二叉树特性的方式，插入到堆的最后一层；
对这个堆进行调整，让新插入的节点与父节点进行对比，以大顶堆为例，如果子节点的值大于父节点，则交互两个节点。然后不断地向上调整，最后使得全部节点满足此关系。这个过程通常称为“向上堆化”。
代码实现：
public class Heap{
private int[] a;//数组，下标从1开始存储
private int n;//堆中可以存储的最大数据的个数
private int count;//堆中已存储的数据个数
//构造方法
public Heap(int capacity){
a = new int[capacity+1];
n = capacity;
count = 0;
}
//堆的插入
public void insert(int data){
//判断堆中容量是否充足
if(count >= n){
return;
}
//如果容量充足，就将新元素放到已有数据的后面一位
++count;
a[count] = data;
int i = count;
//向上堆化
while(i/2 >= 1){
if(a[i]>a[i/2]){
//交换
swap(a,i,i/2);
i = i/2;
}
}
}
}
2、堆的删除
先将堆顶的元素移除，把数组最后的元素放到堆顶；
从上到下调整堆，以大顶堆为例，如果当前的节点的值小于子节点，则进行交换。不断重复这一步骤，直到所有节点都满足大顶堆的关系。
代码实现：
public void remove(){
if(count == 0) return;
a[1] = a[count];
--count;
//向下堆化
heapify(a,1,count);
}
public void heapipfy(int[] a, int i, int n){
while(true){
//maxPos记录了当前节点、左右子节点中值最大的节点下标
int maxPos = i;
//如果有左子节点，且左子节点的值大于当前节点
if(i*2<=n && a[i*2]>a[i]){
maxPos = 2*i;
}
//如果有右子节点，且右子节点的值大于maxPos位置的值
if((i*2+1)<=n && a[i*2+1]>a[maxPos]){
maxPos = 2*i+1;
}
if(i == maxPos) break;
swap(a, i, maxPos);
i = maxPos;
}
}
堆插入和删除的时间复杂度都为O(logn)。因为堆是一棵完全二叉树，其高度不会大于logn，向下堆化或向上堆化的过程是沿着节点所在路径进行比较和交换操作的，每层的比较和交换次数都是常数级别，所以时间复杂度与树高成正比，也就是O(logn)。
3、用堆排序
堆排序的过程分为：①建堆，②删除堆顶元素，将其放置到无序序列的后面一位，③调整堆，④不断重复②和③，直到堆中所有元素被删除。
可以看到，堆排序实际上是原地排序，不用借助另一个数组，就在原数组上操作。
①建堆
下图为建立大顶堆的操作，常用的方法是，从最后一个非叶子节点开始，向下堆化，然后对最后第二个非叶子节点，向下堆化…不断向上推进，直到所有非叶子节点都完成这一操作，这样就保证了所有子树都是堆化状态，那么整棵二叉树就是堆化状态。
代码实现：
public void buildHeap(int[] a, int n){
for(int i=n/2; i>=1; --i){
//向下堆化方法上面已实现
heapify(a,i,n);
}
}
建堆的时间复杂度为O(n)。
推导过程如下：
因为每个非叶节点向下堆化的过程中，在每一层都只存在常数次数的比较和交换，因此，每个非叶节点的堆化时间复杂度与其高度成正比。
上图记录了每一层的节点数和每层的高度，总的堆化时间就是所有非叶节点堆化的时间之和。
由于h=log2n，所以S=O(logn)。故建堆的时间复杂度为O(logn)。
②堆排序
public void heapSort(int[] a, int n){
//首先建堆
buildHeap(a,n);
int k = n;
//只剩1个元素时，无需再操作
while(k > 1){
//将堆顶与堆尾置换
swap(a,1,k);
//无序序列个数减1
--k;
//向下堆化
heapify(a,1,k);
}
}
堆排序的时间复杂度为O(nlogn)。建堆过程O(n)，排序过程中每个节点都堆化一次，即O(nlogn)，故总的时间复杂度为O(nlogn)。
堆排序不是稳定的排序。因为将堆顶元素和堆尾元素进行交换的过程中，可能会改变值相同数据的原始顺序。
堆排序 VS 快速排序：
- 堆排序不是顺序访问。比如堆化的时候，数组下标都是跳着访问的（按照树的路径向下访问），使得被访问的数据不具有局部性，对CPU缓存不友好；而快速排序的数据访问是顺序的。
- 堆排序的交换次数大于快速排序。建堆的过程中会打乱数组元素的原始顺序，可能导致原数据逆序度降低。而快速排序每轮排序都会降低数据逆序度，因此交换次数不会大于逆序度。
四、堆的应用
1、优先级队列
具有优先级的队列，出队时不再按照先进先出的顺序，而是按照一定的优先级，优先级高的元素先出队。这非常符合堆的特性，因为堆顶元素通常是最大或者最小的元素。
优先级队列入队一个元素，相当于堆的插入；优先级队列出队一个元素，相当于堆的删除。
java中 PriorityQueue 就是常见的优先级队列。
下面代码为 jdk 的 PriorityQueue 的一个插入操作，相当于堆的插入中的向上调整。该方法没有采用交换元素的方式，更为高效。
private static <T> void siftUpComparable(int k, T x, Object[] es) {
Comparable<? super T> key = (Comparable<? super T>) x;
// k为新节点的插入位置
while (k > 0) {
//取得父节点的位置，使用右移运算。
int parent = (k - 1) >>> 1;
// 取得父节点的值
Object e = es[parent];
// key >= e说明已经按照升序排序，跳出循环
if (key.compareTo((T) e) >= 0)
break;
// 将父节点的值放到k的位置
es[k] = e;
// k指向父节点的位置，继续向上调整
k = parent;
}
// 最后k的位置就是要插入的位置
es[k] = key;
}
优先级队列的其他方法可参考https://blog.csdn.net/qq_38293564/article/details/80586040
2、Top K问题
对于静态数据集合，比如在包含 n 个元素的数组中，查找前 K 大数据，维护一个大小为K的小顶堆即可。
操作步骤：
①先将数组中前K个元素放到另一个大小为K的数组中，并将其堆化成一个小顶堆。
②然后从K+1个元素开始，进行顺序遍历，如果K+1开始的元素大于堆顶元素，就把堆顶元素删除，把该数组元素插入到堆中；否则，什么都不做，继续遍历数组的下一个元素。
③数组遍历完成，小顶堆中的数据就是Top K的数据。
对于动态数据集合，即存在添加数据的操作。
操作步骤：
①跟静态数据集合的操作一样，建立一个小顶堆，小顶堆中的数据就是初始Top K的数据。
②每次添加数据的时候，同时将这个元素与堆顶元素进行比较，如果大于堆顶元素，就把堆顶元素删除，把该数组元素插入到堆中；否则，什么都不做。
这样，堆中的数据将一直保持Top K。
3、求中位数
长度为n的数组，如果n为奇数，则n/2+1的位置就是中位数；如果n为偶数，则n/2或者n/2+1的位置就是中位数。
很明显，中位数的左侧都是比中位数小，中位数的右侧都是比中位数大。
可以用两个堆来求中位数，如果n为偶数，将前n/2个元素放入到一个大顶堆中，将后n/2个元素放入到一个小顶堆中；如果n为奇数，则将前n/2+1个元素放入到一个大顶堆中，将后n/2个元素放入到一个小顶堆中。此时大顶堆(奇数时)或者两个堆(偶数时)的堆顶将呈现为中位数。
如果数组中存在动态添加元素的操作，中位数不断地变化，那么在添加元素时，如果新元素小于等于大顶堆的堆顶元素，则将其插入到大顶堆；如果大于大顶堆的堆顶元素，则插入到小顶堆。但是，这种做法可能会导致两个堆不平衡，此时只需要在每次插入操作后，对两个堆进行调整，将数量多的堆的堆顶元素不断移动到数量少的堆，直到两个堆平衡。
插入数据时堆化操作的时间复杂度为O(logn)，取中位数的操作为O(1)。
求中位数是用两个堆平分一个数组，如果是想取其他比例的数据，也是可以采用这种方法，只要将两个堆按照给定的比例分配数据即可。
参考资料：极客时间《数据结构与算法：堆和堆排序》