堆排序实现原理解释及思考
/**
* @author https://www.cnblogs.com/chengxiao/p/6129630.html
*/
public class Heap {
public static void main(String []args){
int []arr = {7,8,9,6,3,4,5,2,1,10};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
//1.构建大顶堆
for(int i=arr.length/2-1;i>=0;i--){
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr,i,arr.length);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for(int j=arr.length-1;j>0;j--){
//将堆顶元素与末尾元素进行交换
swap(arr,0,j);
//重新对堆进行调整
adjustHeap(arr,0,j);
}
}
/**
* 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
* @param arr
* @param i
* @param length
*/
public static void adjustHeap(int []arr,int i,int length){
//先取出当前元素i
int temp = arr[i];
//从i结点的左子结点开始，也就是2i+1处开始
for(int k=i*2+1;k<length;k=k*2+1){
//如果左子结点小于右子结点，k指向右子结点
if(k+1<length && arr[k]<arr[k+1]){
k++;
}
//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
if(arr[k] >temp){
arr[i] = arr[k];
i = k;
}else{
break;
}
}
//将temp值放到最终的位置
arr[i] = temp;
}
/**
* 交换元素
* @param arr
* @param a
* @param b
*/
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}堆排序处理顺序的特点是升序使用大顶堆，降序使用小顶堆。
大顶堆（又叫大根堆，最大堆）：
子节点的值一定小于父节点。
即下图中，(1)的值大于(2)、(3)的值
这实际上是误解了堆排序的实现方式，因为堆排序没有进行横向排序的。即(2)和(3)
没有固定的大小关系。
堆排序的实现原理：
将数组看作一个二叉树。数组从左至右依次对应二叉树从上至下从左至右的元素，如下图是一个
长度为12的数组对应的二叉树示意图，数字为对应数组的下标。
1. 首先从末尾父节点(5)开始，比较两个子节点和父节点的大小，将最大值和父节点交换。然后按(4)，(3)，(2)，(1)，(0)
的顺序一直遍历到根节点。此时得到一个大顶堆。
2. 在大顶堆中，根节点(0)的值一定是最大值。所以此时将根节点的值置于末尾。【即交换(0)和(11)的值】
3. 再次基于剩下的元素构建大顶堆，并将根节点值置于当前末尾。。。。
这样做在第二次开始每一次构建大顶堆时，除开顶层元素a，第二层开始都是构建好的大顶堆，
不需比较所有元素，只需要不停交换a和剩下旁支中较大的元素即可。
如下图是第二次比较及交换的其中一种情况。
数学思考：
为什么最末父节点的坐标为array.length/2-1?
由于数组的起始坐标为0，我们可以简单地理解一个元素的坐标为它之前元素的总个数。
二叉树可按每层的元素个数转换为一个基数为1，比值为2的等比数列（除开叶子层）；
可得第n层的元素个数为2^(n-1)
1~n层的元素个数和为2^(n-1)-1
以上图为例：
此时，最末父节点所在层n为第三层，最末父节点的子节点数count =1；
由等比数列性质可知：
该节点之前的元素个数为： 2^(n-1)-1+(x-count)/2;
该节点之后的元素个数为： 2^(n-1)-1-(x-count)/2-1+x;
设m = 2^(n-1) -1 +x/2
则该节点之前的元素个数为： m-count/2
该节点之后的元素个数为：m+count/2
array.length = 节点之前元素+节点+节点之后元素 = 2m+1
m = (array.length-1)/2
可得该节点下标为其之前的元素个数：
(array.length -1)/2 -count/2..................................................................(1)
由于java浮点数转int总是截断小数点后的数（即1/2取值为0）：
若count =1：
则array.length为偶数;array.length-1为奇数；
(array.length-1)/2 = (array.length)/2 -1;
同时count/2舍去；
(1)式可转换为 array.length/2 -1;
若count = 2 :
则array.length为奇数;array.length-1为偶数;
(array.length-1)/2 = (array.length)/2;
count/2 = 1;
(2)式也可转换为array.length/2 - 1;
为什么某节点的左子节点的坐标 = 该节点坐标i*2+1？
将上个问题的最末父节点看作二叉树中的某一节点，则上个问题中count=1情况下的array.length即为子节点的坐标。
可得关系：
（子节点坐标-1）/2 = 父节点坐标。
即 父节点坐标的左子节点坐标 = 父节点坐标 * 2 + 1