堆的定义

堆是一种数据结构，一种叫做完全二叉树的数据结构。

堆的性质

这里我们用到两种堆，其实也算是一种。

大顶堆：每个节点的值都大于或者等于它的左右子节点的值。

小顶堆：每个节点的值都小于或者等于它的左右子节点的值。

把这种逻辑结构映射到数组中，数组arr逻辑上就是一个堆。

从这里我们可以得出以下性质

对于大顶堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

对于小顶堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

堆排序的基本思想

1、将要排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；

2、将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；
3、重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。

那么，该如何知道最后一个非叶子节点的位置，也就是索引值？

对于一个完全二叉树，在填满的情况下（非叶子节点都有两个子节点），每一层的元素个数是上一层的二倍，根节点数量是1，所以最后一层的节点数量，一定是之前所有层节点总数+1，所以，我们能找到最后一层的第一个节点的索引，即节点总数/2（根节点索引为0），这也就是第一个叶子节点，所以第一个非叶子节点的索引就是第一个叶子结点的索引-1。那么对于填不满的二叉树呢？这个计算方式仍然适用，当我们从上往下，从左往右填充二叉树的过程中，第一个叶子节点，一定是序列长度/2，所以第一个非叶子节点的索引就是arr.length / 2 -1。

现在找到了最后一个非叶子节点，即元素值为2的节点，比较它的左右节点的值，是否比他大，如果大就换位置。这里因为1<2，所以，不需要任何操作，继续比较下一个，即元素值为8的节点，它的左节点值为9比它本身大，所以需要交换

java代码实现

java

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {8, 1, 6, 2, 5, 3, 7, 4};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
        //[1, 2, 3, 4, 5, 6, 7, 8]
    }

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int len = arr.length;
        // 构建大顶堆，这里其实就是把待排序序列，变成一个大顶堆结构的数组
        buildMaxHeap(arr, len);

        // 交换堆顶和当前末尾的节点，重置大顶堆
        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
    }

    private static void buildMaxHeap(int[] arr, int len) {
        // 从最后一个非叶节点开始向前遍历，调整节点性质，使之成为大顶堆
        for (int i = (int) Math.floor(len / 2) - 1; i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private static void heapify(int[] arr, int i, int len) {
        // 先根据堆性质，找出它左右节点的索引
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // 默认当前节点（父节点）是最大值。
        int largestIndex = i;
        if (left < len && arr[left] > arr[largestIndex]) {
            // 如果有左节点，并且左节点的值更大，更新最大值的索引
            largestIndex = left;
        }
        if (right < len && arr[right] > arr[largestIndex]) {
            // 如果有右节点，并且右节点的值更大，更新最大值的索引
            largestIndex = right;
        }

        if (largestIndex != i) {
            // 如果最大值不是当前非叶子节点的值，那么就把当前节点和最大值的子节点值互换
            swap(arr, i, largestIndex);
            // 因为互换之后，子节点的值变了，如果该子节点也有自己的子节点，仍需要再次调整。
            heapify(arr, largestIndex, len);
        }
    }

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

复杂度

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。

最好和最坏的情况时间复杂度都是O(nlogn)，空间复杂度O(1)。