没有一身好内功，招式再多都是空;算法绝对是防身必备，面试时更是不可或缺；跟着算法渣一起从零学算法

定义

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆

堆是一棵顺序存储的完全二叉树

其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。

其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。

举例来说，对于n个元素的序列{R0, R1, … , Rn}当且仅当满足下列关系之一时，称之为堆：

(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)

(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

其中i=1,2,…,n/2向下取整;

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

完全二叉树

完全二叉树的定义是建立在满二叉树定义的基础上的，而满二叉树又是建立在二叉树的基础上的。

二叉树

二叉树是树的特殊一种，具有如下特点：

每个结点最多有两颗子树，结点的度最大为2。
左子树和右子树是有顺序的，次序不能颠倒。
即使某结点只有一个子树，也要区分左右子树。

满二叉树

所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树。就是完美圆满的意思，关键在于树的平衡

根据满二叉树的定义，得到其特点为：

叶子只能出现在最下一层。
非叶子结点度一定是2.
在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

完全二叉树

对于一个树高为h的二叉树，如果其第0层至第h-1层的节点都满。如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边。这样的二叉树就是一棵完全二叉树

在上图中，树1，按层次编号5结点没有左子树，有右子树，10结点缺失。树2由于3结点没有字数，是的6,7位置空挡了。树3中结点5没有子树。

完全二叉树

上图就是一个完全二叉树

算法

利用堆顶记录的是最大(以大顶堆为例)关键字这一特性，每一轮取堆顶元素放入有序区，就类似选择排序每一轮选择一个最大值放入有序区，可以把堆排序看成是选择排序的改进。

将初始待排序关键字序列(R0,R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[0]与最后一个元素R[n]交换，此时得到新的无序区(R0,R1,R2,……Rn-1)和新的有序区(Rn)；
由于交换后新的堆顶R[0]可能违反堆的性质，因此需要对当前无序区(R0,R1,R2,……Rn-1)调整为新堆

不断重复此2、3步骤直到有序区的元素个数为n-1，则整个排序过程完成

演示

由一个无序序列建成一个堆
输出堆顶元素之后，调整剩余元素成为一个新的堆

1.构造堆

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

数组是一个无序结构

因为(n/2-1)~0的节点才有子节点，n=5,(n/2-1) = 1 即1 0节点才有子节点

所以将1 0节点从下到上，从右到左的与它自己的子节点比较并调整最终形成大顶堆

1. 节点1和它的子节点3 4的元素进行比较，最大者作为父节点

2. 将节点0和它的子节点1 2的元素进行比较，最大者为父节点

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

构造完成将一个无需序列构造成了一个大顶堆

2. 调整堆

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

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

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

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

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

实现

 /**
 *
 * a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

 　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

 　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

 * 整个排序过程，就是构造堆的过程
 *
 * 这儿写得利于理解一点，把最后一步改掉，循环从数组中把第一位取出来放到新数组，剩余的再去构造堆
 * @param array
 */
static void heapSort(int []array) {
    //原始数组
    int [] oriental = Arrays.copyOf(array,array.length);
    //最终排序好的数组
    int [] result = new int[array.length];

    int length = array.length;
    for ( int i = 0;i< length;i++) {
        //1.构造堆
        buildHeap(array);
        //构建完array[0]就是最大的元素,取出来放到排序好的数组
        result[i] = array[0];
        //[0]取走之后，一个新数组，再去构造堆
        array = Arrays.copyOfRange(array, 1,length-i);
    }
    System.out.println("finish:"+ Arrays.toString(result));
}

/**
 * 构造椎
 * @param array
 */
static void buildHeap(int []array) {
    //(n/2-1)~0的节点才有子节点
    for (int i= array.length/2 -1 ;i>=0;i--) {
//            System.out.println("i:"+i);
//            System.out.println("start:"+ Arrays.toString(array));
        int k = i;
        for (int left = k * 2 + 1; left < array.length; left = k * 2 + 1) {
           // System.out.println("build:"+ Arrays.toString(array));
            int max = left;
            int right = left + 1;
            //有右节点
            if (right < array.length) {
                if (array[right] > array[left]) {
                    max = right;
                }
            }
            //max是left子节点,那就交换左子节点与k
            if (array[max] > array[k]) {
                swap(array, max, k);
                // 下面就是非常关键的一步了
                // 如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？
                // 所以，循环对子节点所在的树继续进行判断
                k = left;
            } else {
                break;
            }
        }
    }
    //System.out.println("  end:"+ Arrays.toString(array));
}

详细代码：
https://github.com/zhuxingsheng/javastudy/tree/master/src/main/java/com/jack/algorithms/sort

复杂度

Best	Average	Worst	Memory	Stable
n log(n)	n log(n)	n log(n)	1	No

参考资料

图解排序算法(三)之堆排序

图解堆排序

新生代农民工的自我修养

算法渣-排序-堆排序

定义

堆

完全二叉树

二叉树

满二叉树

完全二叉树

算法

演示

1.构造堆

2. 调整堆

实现

复杂度

参考资料