堆排序（HeapSort）简单实现

（二叉）堆是一个数组（不要把此处的堆与内存区域的堆内存混淆了）此处是指数据结构，二叉堆可以近似看成一个完全二叉树，将数组中元素从上自下，从左自右插入到完全二叉树中。堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

利用完全二叉树可以清晰地看出根节点与左右子孩子的关系：准确的说是看出根节点与左右还在在数组中下标的关系。

举个例子：

数组a：

转换为完全二叉树：

仔细观察数组位置于在完全二叉树中的位置会发现：假设父节点为i，左孩子：2i+1 右孩子：2i+2

(此处是完全二叉树从0开始计算，如果从1开始计算，相应的等式应该变为：左孩子2i 右孩子：2i+1)

找到这个关系可以在不使用指针的情况下计算数组索引在数的上下层进行移动。此处可以想到将完全二叉树使用数组进行保存。

堆可以分为：最大堆 和 最小堆

最大堆除了满足堆的基本性质之外，除了根节点的以外所有的节点都满足：父节点的值 >=子节点的值

上面那张图片就是一个最大堆。最大堆可以被用来实现对于数组的递增排序。

最小堆除了满足堆的性质之外，类比最大堆，父节点的值 <=子节点的值，最小堆常用来构造优先队列

（1）首先构造出最大堆

（2）将最大堆 堆顶元素于末尾元素进行交换

（3）除了最后一个元素之外的n-1个元素继续进行（1）（2）的步骤直到n=0；

根据最大堆的性质：父节点值大于子节点值 构造最大堆时我们应该使用自低向上进行构造

• 需要从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2=5/2)不断向上调整，
• 如果左右孩子中存在数值大于父节点的，则将父节点于左右孩子中最大值进行交互，（一定是左右孩子最大值），如果左右孩子都小于父节点则不进行交换。

数组a：

（1）从最后一个非叶节点开始，14为最大值的孩子节点且大于父节点，所以交换14和12

（2）排序倒数第二个非叶节点

（3）因为8 13 12这颗子树不满足要求，所以得继续向下调整

（3）将堆顶的元素于最后一个元素进行交换

（4）对剩下n-1个元素重复上述过程，直至n为0

具体代码：

    public static void adjustHeap(int a[], int parent, int length) {
        int left = 2 * parent + 1;
        while (left <= length) {
            int right = left + 1;
            int largest = right <= length && a[left] < a[right] ? right : left;
            if (a[parent] < a[largest]) {
                a[parent] = a[parent] ^ a[largest];
                a[largest] = a[parent] ^ a[largest];
                a[parent] = a[parent] ^ a[largest];
                parent = largest;
                left = 2 * parent + 1;
            } else
                break;
        }
    }
    public static void heapSort(int a[]) {
        for (int i = a.length >> 1; i >= 0; i--)
            adjustHeap(a, i, a.length - 1);
        //System.out.println(a[0]);
        for (int i = a.length - 1; i > 0; i--) {
            swap(a, 0, i);
            adjustHeap(a, 0, i - 1);
        }
    }

i > 0; i–) {
swap(a, 0, i);
adjustHeap(a, 0, i - 1);
}
}