一、什么是堆？
堆是一种特殊的树，堆要满足下面两点。
1、堆是一个完全二叉树；
2、堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
通过下图可以更好理解：
根据堆的要求我们可以知道，堆有两种形式；对于每个节点的值都大于等于子树中每个节点值的堆叫大顶堆，对于每个节点的值都小于等于子树中每个节点值的堆，叫作小顶堆。
二、怎么实现一个堆？
要实现一个堆最重要的一个操作就是堆化，堆化有两种方法。（下面的案例我们用小顶堆来演示）
这里有个小提示: 我们用数组来实现堆时，一般都假设堆中的数据是从数组下标为1的位置开始存储，如果节点的下标是i，那左子节点的下标就是2 * i,右子节点的下标就是2 * i + 1，父节点的下标就是 i/2；（如果从0开始的话，下标会多一次运算。）
1、从下往上的堆化
让新插入的节点与父节点对比大小。如果不满足子节点大于等于父节点，就互换两个节点。一直重复这个过程，直到父子节点之间满足堆的第二个要求。
我们用代码实现如下：
public class ArrayHeap(
// 数组，从下标1开始存储数据
private int[] root;
// 堆的大小
private int size;
// 堆已经存储了多少个数据
private int count;
public ArrayHeap(int capacity){
root = new int[capacity +1];
size = capacity;
count = 0;
}
/**
* 插入数据
*
* @param data 要插入的数据
* @return 返回是否成功
*/
public boolean insert(int data){
// 堆满了
if(count >= size) return false;
root[++count] = data;
// 堆化
heapify(root, count);
reutrn true;
}
/**
* 自下而上堆化
*
* @param arr 数组
* @param i 节点下标
*/
public void heapify(int[] arr, int i){
while( i/2 > 0 && a[i] < arr[i/2]){ // 当节点小于父节点时
// 交换
swap(arr, i, i/2);
// 继续判断
i = i/2;
}
}
// 交换两个位置的值
private void swap(int[] arr, int u, int v){
int temp = arr[u];
arr[u] = arr[v];
arr[v] = temp;
}
}
2、从上往下的堆化
我们把最后一个节点放到堆顶，然后利用同样的父子节点对比方法，对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。
这里我们实现移除堆顶节点，代码如下：
/**
* 删除堆顶元素
*/
public int removeMin(){
// 堆中没有数据
if(count == 0) return -1;
int data = root[1];
// 把最后一个节点放到堆顶
root[1] = root[count]
// 堆化
heapifyMin(root, count, 1);
return data;
}
/**
* 自上而下的堆化操作
*
*@param arr 数组
*@param n 堆中元素个数
*@param i 当前节点
*/
public void heapifyMin(int[] arr, int n, int i){
while(true){
// 找出要与节点 i 交换的子节点
int minPos = i;
if(i*2 <= n && arr[i*2] < arr[minPos]){
minPos = i * 2;
}
if(i*2 + 1 <= n && arr[i*2 + 1] < arr[minPos]){
minPos = i * 2 + 1;
}
// 如果没有要交换的，说明子节点都大于节点i
if(i == minPos){
return;
}
// 互换位置
swap(arr, i, minPos);
i = minPos;
}
}
3、建堆和排序
不借助另一个数组，就在原数组上操作。有两种思路。
第一种，把元素一个个往堆中插入，利用上面的插入操作，就可以组成堆。
第二种，从后往前处理数组，并且每个数据都是从上往下堆化，跟上面删除堆顶的堆化操作一样。
第二种实现代码如下：
public void buildHeap(int[] arr, int n){
for(int i = n/2; i >= 1; i--){
// 调用上面删除堆顶的堆化操作
heapifyMin(arr, n, i);
}
}
建堆的实际时间复杂度是O(n), 按道理来说每个节点堆化的时间复杂度是O(logn)，叶子节点是不需要堆化的，所以需要堆化的节点是n/2 + 1个节点，那是不是堆化的总时间复杂度就是O(nlog)呢。我们来推导一下。
| 层数 | 高度 | 节点个数 | 每层的时间复杂度 |
|---|---|---|---|
| 1 | h | 20 | 1* h |
| 2 | h-1 | 21 | 2 * (h-1) |
| 3 | h-2 | 22 | 4 * (h-2) |
| 4 | h-3 | 23 | 8 * (h-2) |
| ... | ... | ... | ... |
| h-1 | 1 | 2h-1 | 2h-1 * 1 |
总的时间复杂度 = 每层的时间复杂度之和
f(n) = 1h + 21 * (h-1) + 22 * (h-2)+ 23 * (h-3) + ... + 2h-1 * 1
把两边都乘2
2 * f(n) = 21h + 22 * (h-1) + 23 * (h-2) + 24 * (h-3) + ... + 2h * 1
两个相减
f(n) = -h + 2 + 22 + 2 + 23 + ...+ 2k + ... + 2h-1 +2h = 2h+1 - h -2
因为 h = log2n 代入公式f(n)，就能得到 f(n) = O(n),所以，建堆的时间复杂度就是O(n)。
现在我们把建好堆的数组进行排序，这个过程有点类似上面删除堆顶元素，当堆顶的元素移除之后，把下标为n的元素放到堆顶，将移除的元素放到下标n的位置，将剩下n-1个元素重新构建成堆。一直重复到下标为1的一个元素，排序工作就完成了。代码如下：
/**
* 排序
* @param arr 数组
* @param n 数据的个数，数组arr中的数据从下标1到n的位置。
*/
public static void sort(int[] arr, int n){
buildHeap(arr, n);
for(int i = n; i > 1; i--){
// 交换位置
swap(arr, 1, i);
// 重新堆化
headify(arr, i, 1);
}
}
三、堆的应用
1、优先级队列
我们知道队列最大的特性就是先进先出。但在优先级队列，是按照优先级来，优先级最高的，最先出队。
一个堆就可以看作一个优先级队列 。在优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素（这里的堆是大顶堆）；常见案例有 合并有充小文件、高性能定时器
2、利用堆求 Top K
如何在一个包含n个数据的数组中，查找前K大数据呢？先维护一个大小为K的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。等遍历完之后，堆中数据就是前K大元素。
2、利用堆求中位数
借助堆这种数据结构，我们不用排序，就可以非常高效地实现求中位数的操作。具体实现代码如下：
/**
* 用堆求数组的中位数；维护两个堆，大顶堆中存储前半部分数据，
* 小顶堆中存储后半部分数据。且小顶堆中的数据都大于大顶堆中的数据
*
* @param arr 数组
* @param n 数据个数
* @return 中位数
*/
public int getMedian(int[] arr, int n) {
// 计算两个顶堆的大小
int minSize = n / 2;
int maxSize = n / 2;
// 如果数组大小是奇数，大顶堆存储 n/2+1个数据
// 这样就不管数组大小是奇偶，中位值都是大顶堆的第一个值
if (n % 2 == 1) {
maxSize = n / 2 + 1;
}
// 大顶堆
ArrayHeap heapMax = new ArrayHeap(maxSize);
// 小顶堆
ArrayHeap heapMin = new ArrayHeap(minSize);
// 往两个堆中添加数据,利用小顶堆的特性把数组前minSize大的值放入heapMin中
for (int i = 0; i < n; i++) {
// 如果heapMin满了
if (heapMin.isFull()) {
int temp = arr[i];
// 如果当前值大于heapMin第一个值，说明heapMin中的值还不是数组中最大的值
if (arr[i] > heapMin.root[1]) {
// 把heapMin第一个值替换成当前值
temp = heapMin.root[1];
heapMin.root[1] = arr[i];
// 重新堆化heapMin
heapMin.heapipyMin(heapMin.root, minSize, 1);
}
// 把小顶堆踢出来的值或者小于小顶堆第一个值添加到hemapMax中
heapMax.insertMax(temp);
} else {
// 把数据插入heapMin
heapMin.insertMin(arr[i]);
}
}
return heapMax.root[1];
}
