堆排序（heapsort）是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆与小根堆。是完全二叉树。

满二叉树与完全二叉树

满二叉树：除了叶子节点之外的每一个节点都有两个孩子，并且所有的叶子都在同一层上，这样的二叉树称为满二叉树。

1.叶子节点只能出现在最下一层，出现在其他层就不可能达成平衡。2.非叶子节点的度一定是2（度指拥有的子树数目）3.在同样深度的二叉树中，满二叉树的节点个数最多，叶子数最多。

完全二叉树：除了最后一层之外的其他每一层节点个数都达到最大个数，并且一层节点都保持向左对齐，这就是完全二叉树。

1.叶子节点只能出现在最下层和次下层2.最下层的叶子节点集中在树的左部3.如果节点的度为1，则该节点只有左孩子，即没有右子树。

满二叉树一定是完全二叉树，反过来不成立。

简单来说，堆排序就是将数据看成完全二叉树、根据完全二叉树的特性来进行排序的一种算法。

最大堆要求节点的元素都要不小于其孩子，最小堆要求节点的元素都不大于其孩子。那么处于最大堆的根节点的元素一定是这个堆中的最大值。

那么，完全二叉树与堆有什么关系呢？

我们假设有一棵完全二叉树，在满足作为完全二叉树的基础上，对于任意一个拥有父节点的子节点，其数值均不小于父节点的值；这样层层递推，就是根节点的值最小，这样的树，称为小根堆。

同理，又有一棵完全二叉树，对于任意一个子节点来说，均不大于其父节点的值，如此递推，就是根节点的值是最大的，这样的数，称为大根堆。

如上图，左边就是大根堆；右边则是小根堆，这里必须要注意一点，只要求子节点与父节点的关系，两个节点的大小关系与其左右位置没有任何关系。

明确下大根堆，小根堆的概念，继续说堆排序。

现在对于堆排序来说，我们先要做的是，把待排序的一堆无序的数，整理成一个大根堆，或者小根堆，下面讨论以大根堆为例子。

给定一个列表array=[16,7,3,20,17,8]，对其进行堆排序（使用大根堆）。

接下来内容是转载部分，自己绘图功底太差：其中绿色部分为自己的注解。

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

　　a.假设给定无序序列结构如下

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

此处必须注意，我们把6和9比较交换之后，必须考量9这个节点对于其子节点会不会产生任何影响？因为其是叶子节点，所以不加考虑；但是，一定要熟练这种思维，写代码的时候就比较容易理解为什么会出现一次非常重要的交换了。

4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

在真正代码的实现中，这时候4和9交换过后，必须考虑9所在的这个节点位置，因为其上的值变了，必须判断对其的两个子节点是否造成了影响，这么说不合适，实际上就是判断其作为根节点的那棵子树，是否还满足大根堆的原则，每一次交换，都必须要循环把子树部分判别清楚。

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

牢记上面说的规则，每次交换都要把改变了的那个节点所在的树重新判定一下，这里就用上了，4和9交换了，变动了的那棵子树就必须重新调整，一直调整到符合大根堆的规则为截。

此时，我们就将一个无序序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

这里，必须说明一下，所谓的交换，实际上就是把最大值从树里面拿掉了，剩下参与到排序的树，其实只有总结点的个数减去拿掉的节点个数了。所以图中用的是虚线。

b.重新调整结构，使其继续满足堆定义

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

下面，附上我的代码。

堆排序代码

public static void sort(int array[]){ /** * 从最后一个非叶子节点开始建堆，对整棵树进行大根堆的调整,最后将最大的数调整到了根节点 */ for (int i=array.length/2-1;i>=0;i--){ adjustHeap(array,i,array.length); } /** * 上面建堆结束，下面开始排序逻辑 * 这里为什么array.length - 1?因为最大下标为len-1 */ for (int j=array.length-1;j>0;j--){ swap(array,0,j); adjustHeap(array,0,j); } } public static void adjustHeap(int[] array,int i,int length){ int temp = array[i]; //i为子树的根节点，k初始值为子树根节点的左孩子节点 for (int k=2*i+1;k<length;k=2*k+1){ //如果还有右节点并且右节点比左节点更大，则k++，即k++后k为右节点的索引 //k+1<length 保障了换到最后面的数不会再被访问到了 if(k+1<length && array[k]<array[k+1]){ k++; } //如果右节点大于子树根节点，则右节点交换至根节点 if (array[k] > temp){ swap(array,i,k); //如果子节点更换了，那么以子节点为根的子树会不会受到影响呢？ //所以循环对以子节点为根的树进行判断 i=k; }else { break; } } } /** * 交换！ * @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; }

堆排序的最好、最坏、平均时间复杂度都是O(nlogn)，空间复杂度为O(1)，是不稳定的排序算法

运行时间主要消耗在构造堆和重建堆时的反复筛选上。

构造堆的时间复杂度为O(n) 重建堆时时间复杂度为O(logn)。

所以总体就是O(nlogn)。 不适合排序序列个数较少的情况。