彻底搞懂堆排序

一、准备知识

1.堆

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
  
• 堆总是一棵完全二叉树。
  

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆是线性数据结构，相当于一维数组，有唯一后继。

堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

2.最大堆

把根节点最大的堆叫最大堆。

二、堆排序的思想

堆排序是将一个数组通过数组下标关系虚构出一个最大堆，这样这个最大堆的根节点是最大的，然后将这个堆的最后一个节点和根节点交换，这个最大值就到了数组的最后，然后数组的长度减一，减一后的数组在调整顺序，使其再次成为一个最大堆，这是根节点就是第二大的元素，然后将重复上面的步骤，知道全部交换完毕，数组就排好了顺序。

三、排序

1.将数组构造为一个虚拟的最大堆

通过下标来构造这个最大堆。

（1）数组下标和堆元素的对应关系。

通过上面的图，我们可以分析出，一个节点，我们可以使用(n-1)/2来计算它的父节点的坐标、使用2*n+1来计算它的左节点的坐标、使用2*n+2来计算它的右节点的坐标。

（2）构造最大堆

遍历整个数组，构造一个最大堆，每次插入一个数，然后使堆重新成为一个最大堆。构造过程如下：

• 首先将1加入堆，这时堆中只有一个元素，数组现在为[1,2,3,4,5,6,7]。
  
• 将2加入堆中，计算2的父节点(1-1)/2=0,2的父节点是数组下标为0的元素。这时候2成为了1的左节点，根节点小于子节点，不满足最大堆的定义，所以调整这个堆，让根节点最大，所以1,2交换位置,数组现在为[2,1,3,4,5,6,7]。
  
• 将3加入堆中，计算3的父节点(2-1)/2=0,3的父节点是数组下标为0的元素。这时候3成为了2的右节点，发现根节点2小于3，调整堆，将根节点2和3交换位置，现在数组为[3,1,2,4,5,6,7]。
  
• 重复上面的步骤，将每一个元素加入这个堆，加入一个节点后，对比加入的节点和它的父节点的大小，如果新加入的节点大于它的父节点，则将两者交换，然后在比较交换后的节点和它的父节点的大小，知道使堆重新成为一个最大堆。
  构造过程代码：
  

2. 通过堆的结构调整来排序。    

通过上面的构造，我们已将一个数组通过下标关系构造成为了一个虚拟的最大堆，这时候我们知道这个最大堆的根节点(也就是数组的第一个元素)现在肯定是所有数字中最大的一个，然后根据这个已知关系调整这个堆，来达到排序的目的。

调整过程如下：

• 将数组的第一个元素和数组的最后一个元素交换位置，这样最大的那个数就到了数组的最后，然后数组长度减一，将最后一个数排除在外，剩余的数重新调整顺序，重新成为一个最大堆，这样根节点就变成了一个次大的元素。

• 然后再次将根元素和现在的最后一个元素(原数组的倒数第二个元素)交换位置，数组长度在减一，然后重新调整堆使其再次成为一个最大堆。

• 重复上面的步骤，直到所有的数字都调整完毕，这时数组就排好了顺序。

数组调整过程：

• 找出当前节点和它的左节点、右节点三者中最大的那个节点，如果最大的节点是它自己则不做任何调整，如果最大的节点是它的左节点或者右节点，则和该节点交换位置，然后将交换后的节点作为当前节点在重复判断。
  
• 重复上面的步骤，使其重新成为一个最大堆。
  

调整过程代码如下:

四、完整代码

publicclassHeapSort {
publicvoidheapSort(int[] arr) {
for (inti=0; i<arr.length; i++) {
heapInsert(arr, i);
                     }
intheapSize=arr.length;
while (heapSize>1) {
heapify(arr, --heapSize);
                     }
                 }
privatevoidheapInsert(int[] arr,inti) {
intlast= (i-1) /2; //计算父节点while (arr[i] >arr[last]) { // 比较当前节点和父节点//调整堆swap(arr,i,last);
//继续判断他的上一层节点是否满足最大堆i=last;
last= (i-1) /2;
                   }
               }
publicvoidheapify(int[] arr, intheapSize) {
swap(arr, 0, heapSize--);
intcur=0;
while (2*cur+1<=heapSize) {
intleft=2*cur+1;
intright=2*cur+2;
intlastMax=heapSize>=right&&arr[left] >arr[right] ?arr[left] >arr[cur] ?left : cur                           : heapSize>=right?arr[right] >arr[cur] ?right : cur :
arr[left] >arr[cur]
?left : cur;
if (lastMax==cur) {
break;
                   }
inttemp=arr[cur];
arr[cur] =arr[lastMax];
arr[lastMax] =temp;
cur=lastMax;
               }
             }
publicvoidswap(int[] arr, inti, intj) {
inttemp=arr[i];
arr[i] =arr[j];
arr[j] =temp;
             }
@Testpublicvoidtest() {
int[] arr= {1,2,3,4,5,6,7};
int[] arr1=Arrays.copyOf(arr, arr.length);
heapSort(arr);
Arrays.sort(arr1);
Assert.assertArrayEquals(arr, arr1);
               }
              }

五、复杂度。

时间复杂度：O(nlogn)

空间复杂度：O(1)