什么是堆？
“堆”是一种常用的数据结构，也是一种特殊的树。我们来看看，到底什么样的树才是堆。堆有如下两点要求，满足这两点要求的，就是一个堆。
1.堆是一个完全二叉树
2.堆中的每个节点值都必须大于等于（或小于等于）其子树每个节点的值。
第一点，堆是完全二叉树。那就意味除了树的最后一层，其他层节点个数都是满的，最后一层的节点都靠左排列。
第二点，换种说法就是，堆中的每个节点都大于等于（或小于等于）其左右节点的值。
对于每个节点值都大于等于子树每个节点的值的堆，称之为“大顶堆”。对于每个节点值都小于等于子树中每个节点值的堆，称之为“小顶堆”。“大顶堆”的第一个元素为最大值，“小顶堆”的第一个元素为最小值。
堆有哪些操作？
完全二叉树比较适合用数组来存储，这样比较节省存储空间。因为不需要存储左右子节点的指针，只要通过数组的下标，就可以很方便的找到一个节点的左右子节点和父节点。
下面是一个大顶堆的例子,数组下标从1开始。
从图中可以看出，对于任意一个下标为i的节点，这个节点的左子节点是下标为 i*2 的节点，右子节点是下标为 i * 2 + 1的节点，父节点是 i / 2 的节点。
知道了如何存储一个堆后，接着看看堆有哪些操作。堆有两个非常核心的操作：往堆中插入一个元素、删除堆顶元素。
1.往堆中插入一个元素
往堆中插入一个元素后，堆结构需要继续满足堆的两个特性。将新元素放到堆最后，如果不符合堆的特性，那就需要进行调整重新满足堆的特性，这个调整的过程叫做“堆化”。
堆化有两种，“从上往下”和“从下往上”。下面使用“从下往上”的方式来实现往堆中插入元素。
“从下往上”这种堆化方式非常简单，新插入的节点与父节点比较大小。如果不满足子节点小于等于父节点，那么就互换两个节点。重复这个过程，直到父子节点之间满足这种关系为止。
根据上面的思路，插入元素的代码可以结合着图示一起看。
public class Heap{
private int[] arr; //二叉树数组
private int count; //堆中已经存储的数据个数
public Heap(int capacity){
arr = new int[capacity + 1];
n = capacity;
count = 0;
}
public void insert(int data){
if(count + 1 >= arr.length){
throw new IllegalArgumentException();
}
count++;
arr[count] = data;
int pos = count;
while (pos / 2 > 0 && arr[pos / 2] < arr[pos]){
swap(pos,pos / 2);
pos = pos / 2;
}
}
}
2.删除堆顶元素
删除堆顶元素后，同样也需要保证堆能够满足那两个特性。删除堆顶元素后，我们可以把堆中最后一个元素放到堆顶。然后利用父子节点对比方法，对于不满足父子节点大小关系的节点，互换两个节点，重复进行这个过程，直到父子节点之间满足二叉堆的特性为止。这里使用的是“从上往下”的方法进行堆化。
根据上面的思路，删除堆顶元素的代码可以结合着图示一起看。
public void removeTop(){
if(count == 0 ){
retun;
}
a[1] = arr[count];
count--;
int pos = 1;
int maxPos = 1;
while(true){
if(pos * 2 <= count && arr[pos * 2] > arr[pos]){
maxPos = pos * 2;
}
if(pos * 2 + 1 <= count && arr[pos * 2 + 1] > arr[pos]){
maxPos = pos * 2 + 1;
}
if(maxPos == pos){
break;
}
swap(arr,pos,maxPos);
pos = maxPos;
}
}
一颗包含n个节点的完全二叉树，树的高度不会超过。堆化的过程是顺着节点的路径进行比较交换，所以堆化的时间复杂度跟树的高度成正比，也就是O(log n)。因为插入和删除都是做的堆化操作，所以他们的时间复杂度都是O(log n)。
堆排序怎么实现？
我们可以借助堆这种数据结构实现的排序算法，就叫堆排序。这种排序算法的时间复杂度很长稳定，是O(n log n)。堆排序的过程可以分为两个步骤，构建堆和排序。
1.构建堆
将待排序的数据构建成堆，构建堆有两种思路。
第一种就是借助前面说的，在堆中插入一个元素。我们可以假设最开始堆中只包含一个下标为1的数据。然后我们调用插入操作，将下标从2到n的数据依次插入到堆中。这样我们就将包含n个数据的数组，组织成了堆。
第二种实现，和第一种思路相反。第一种建堆处理过程是从前往后处理数组数据，每个数据插入堆中，都是从下往上堆化。而第二种实现思路是从后往前处理数组，并且每个数据都是从上往下堆化。
可以参照下面的例子，叶子节点堆化只能和自己比较，所以我们直接从第一个非叶子节点开始，依次堆化就可以。
对照着图示，将建堆的过程翻译成代码。
/**
* 构造堆
*/
private void buildHeap(){
for(int i = count / 2; i>0; i--){
downAdjust(i,count);
}
}
/**
* "从上往下"调整
* @param pos:下沉节点下标
* @param n：堆有效大小
*/
private void downAdjust(int pos,int n){
int maxPos = pos;
while (true){
if(pos * 2 <= n && arr[pos * 2] > arr[pos]){
maxPos = pos * 2;
}
if(pos * 2 + 1 <= n && arr[pos * 2 + 1] > arr[maxPos]){
maxPos = pos * 2 + 1;
}
if(maxPos == pos){
break;
}
swap(pos,maxPos);
pos = maxPos;
}
}
2.排序
经过建堆这个步骤后，数组就是一个标准的大顶堆了。数组中第一个元素是堆顶，也是数组中最大的元素。我们把它和最后一个元素交换，那么最大元素就放到下标为count的位置了。
这个过程类似于“删除堆顶元素”，当堆顶元素删除之后，我们把最后一个元素放到堆顶，然后通过“从上往下”方式堆化，将剩下count - 1个元素重新构建成堆。堆化完成后，再取堆顶元素放到下标是 count - 1位置，一直重复这个过程，直到堆中只剩下下标为1的一个元素，完成排序。
将上面的排序过程，翻译成排序代码。
/**
* 堆排序
*/
public void sort(){
int n = count;
for (int i = count; i > 1 ; i--){
swap(1,i);
downAdjust(1,--n);
}
}
时间复杂度分析
在整个堆排序的过程中，需要极少的临时存储空间。堆排序包括建堆和排序两个操作，构建堆过程的时间复杂度是O(n)，排序过程的时间复杂度是O(n log n)，所以堆排序整体的时间复杂度是O(n log n)。
GitHub 代码地址： 二叉堆
