堆排序：堆排序的思想比较难理解，首先将数据看成是一个二叉树，对数据进行二叉树的建立(建堆)，这个过程也是排序的过程，将最小或最大的值排到根节点上，如果采用最大值，则称为最大堆，反之，称为最小堆
例如：有一个数组为[8,1,4,2,3],将他变为二叉树为：
8
1 4
2 3
要对它进行排序，可以从8开始，和他的左孩子和右孩子比较，将小的那个和本身进行替换，第一次替换变为：
1
8 4
2 3
再以替换的节点作为父节点，和他的左孩子和右孩子比较，将小的和本身那个交换
1
2 4
8 3
另外我们观察索引发现，当前节点索引 * 2 + 1即为左孩子的索引，当前节点索引 * 2 + 2即为右孩子索引
实现代码：
private void createHeap(int[] nums, int size, int index) {
//数组索引：0 1 2 3 4 5 6
//0的左孩子索引是1 ，0的右孩子索引是2
//1的左孩子索引是3，右孩子是4
//2的左孩子索引是5，右孩子是6
//得出：
int leftIndex = 2 * index + 1;//左孩子索引
int rightIndex = leftIndex + 1;//右孩子索引
//将当前节点、左孩子、右孩子的值进行比较，较小的值和当前节点替换
if (leftIndex >= size && rightIndex >= size) {//没有孩子，不用处理了
return;
}
int currentValue = nums[index];
int leftValue = leftIndex < size ? nums[leftIndex] : Integer.MAX_VALUE;//可能没有(代码走到这，左孩子其实不可能没有)
int rightValue = rightIndex < size ? nums[rightIndex] : Integer.MAX_VALUE;//可能没有
if (currentValue <= leftValue && currentValue <= rightValue) {//当前节点已经小了，不用处理
return;
}
if (leftValue < rightValue) {//左孩子替换当前节点
nums[index] = leftValue;
nums[leftIndex] = currentValue;
createHeap(nums, size, leftIndex);
} else {//右孩子替换当前节点
nums[index] = rightValue;
nums[rightIndex] = currentValue;
createHeap(nums, size, rightIndex);
}
}
但是我们发现自上而下建立二叉树，是不可行的
比如：数组为：[8,2,4,1,3]
二叉树为：
8
2 4
3 1
那么调用我们代码后形成的树为：
2
1 4
3 8
最小值1，并没有到达根节点，这时转变思路，不用从根节点开始建立，而是从树的底部开始建立堆，过程为：
先将1，2，3进行排序
8
1 4
3 2
然后1，4，8进行排序
1
8 4
3 2
思想就是从最深度- 1的深度的倒数第一个节点开始倒着建堆，以上面的数据就是从4开始，由于是完全二叉树，所以索引为：(数组大小 - 1) / 2
实现代码：
public void buildHeap(int[] nums) {
for (int i = (nums.length - 1) / 2; i >= 0; i--) {
createHeap(nums, nums.length, i);
}
//取出最小的
int n = nums.length;
while (n > 0) {
System.out.print(nums[0] + " ");
nums[0] = nums[n - 1];
n--;
createHeap(nums, n, 0);
}
}
测试代码：
int[] nums = new int[]{5, 7, 1, 3, 9, 0, 1, 6, 8, 4};
buildHeap(nums);
结果：
0 1 1 3 4 5 6 7 8 9
堆排序本身用来排序性能并不高，但是作为查找的时候性能很高，由于二分查找只针对已经排好序的顺序表，对于大数据量的散列表，推排序就可以出场了，因为推排序的建堆过程，尽可能少的访问节点，减少了对一个节点的重复访问，而又具有二分的思想，相比于其他排序，查找性能非常高
