堆排序
堆的概念：
堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。
堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易存储在数组中，位置看k的节点的父节点位置为（k-1）/2，而它的两个子节点的位置分别为2k+1和2k+2。
上浮和下沉
在堆中，当一个节点比父节点大，那么需要交换这两个节点。交换后可能比它新的父节点还大，因此需要不断的进行比较和交换操作，把这种操作称为上浮。
类似的，当一个节点比子节点小，也需要不断的向下进行比较和交换，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大的那个节点进行交换。
堆排序
把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从头到尾的递增序列，这就是堆排序。
1.构建大顶堆
无序数组建立堆最直接的方法就是从左到右遍历数组进行上浮操作。
2.交换堆顶元素和最后一个元素
交换之后需要对堆顶元素进行下沉操作，重新保持大顶堆状态。
代码实现：
public class Sort{
public static void heapSort(int[]arr){
if(arr==null||arr.length==0)
return;
for(int i=0;i<arr.length;i++){
heapInsert(arr,i); //插入元素构成大顶堆
}
int size=arr.length; //堆的大小
swap(arr,0,--size);//将堆顶元素和最后一个元素交换，堆的大小减1
while(size>0){//调整当前堆，使其变成大顶堆，下沉过程
heapify(arr,0,size);
swap(arr,0,--size);//将堆顶元素和堆里最后一个元素交换，然后堆的大小减1。
}
}
public static void heapInsert(int[]arr,int i){
while(arr[i]>arr[(i-1)/2]){//当前节点大于其父节点，上浮
swap(arr,i,(i-1)/2);
i=(i-1)/2;
}
}
public static void heapify(int []arr,int index,int size){
int left=2*index+1; //左孩子坐标
while(left<size){
int largest=left+1<size&&arr[left]>arr[left+1]?left:left+1;
largest=arr[largest]>arr[index]?largest:index;
if(largest==index){
break;//如果三个数中最大值还是父节点，那么就退出，不用下沉
}
swap(arr,largest,index);
index=largest; //和前面相同的操作,迭代往下沉，直到越界
left=index*2+1;
}
}
public static void swap(int[]arr,int index,int largest){
arr[index]=arr[index]^arr[largest];
arr[largest]=arr[index]^arr[largest];
arr[index]=arr[index]^arr[largest];
}
}
一个堆的高度为logN，因此在堆中插入元素和删除最大元素的复杂度都为logN。
对于堆排序，由于要对N个节点进行下沉操作，所以复杂度为O(NlogN)。
堆排序是原地排序，没有利用额外的空间。