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

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

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

图1

如上图所示，序列R{3, 8, 15, 31, 25}是一个典型的小根堆。

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

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

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

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

堆排序要点

（1）根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。

（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。

当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。

先通过详细的实例图来看一下，如何构建初始堆。

设有一个无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。

图片2

构造了初始堆后，我们来看一下完整的堆排序处理：
还是针对前面提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。

图片3

排序.jpg

根据二叉树性质：
如果一棵树有n个节点的完全二叉树，
如果2i+1>n, 则节点i无左孩子，i为叶子节点，否则，左孩子节点是2i+1.
如果2i+2>n, 则节点i无由孩子，i为叶子节点，否则，右孩子节点是2i+2.

代码实现

    public static void heapSort (int[] list) {
        // 循环建立初始堆
        for (int i=list.length/2-1; i>=0; i--) {
            HeapAdjust(list, i, list.length);
        }
        // 进行n-1次循环，完成排序
        for (int i=list.length-1; i>0; i--) {
            //最后一个元素和第一元素进行交换
            swap(list, 0, i);
            //继续构建堆
            HeapAdjust(list, 0, i);
        }
    }

    public static void HeapAdjust(int[] list, int parent, int len) {
        //temp保存当前父节点
        int temp = list[parent];
        //根据二叉树性质，获取左子树
        int child = 2 * parent + 1;

        while (child < len) {
            //判断是否有右子树，如果大于左子树，选取右子树节点
            if (child + 1 < len && list[child] < list[child+1]) {
                child++;
            }

            //如果父节点大于孩子节点，跳出循环
            if (temp > list[child]) {
                break;
            }

            //把孩子节点赋值给父节点，此时父节点和孩子节点值一样
            list[parent] = list[child];
            parent = child;
            //继续选取左孩子节点向下筛选
            child = 2*child + 1;
        }
        list[parent] = temp;
    }

    public static void swap(int[] list, int i, int j) {
        int temp = list[j];
        list[j] = list[i];
        list[i] = temp;
    }

    public static void main(String[] args) {
        int[] list = {1, 3, 4, 5, 2, 6, 9, 7, 8, 0};
        heapSort(list);
        for (int i=0; i<list.length; i++) {
            System.out.print(list[i] + ", ");
        }
    }

输出结果：
Heap sort:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

时间复杂度是：O(nlogn)