堆排序

堆的定义

堆可以理解为一棵完全二叉树，它可以分为大顶堆和小顶堆。

• 大顶堆：每个节点的值都大于或等于其左右孩子节点的值
• 小顶堆：每个节点的值都小于或等于其左右孩子节点的值

一棵完全二叉树可以由一个数组表示

• 对于节点10，它存储在数组中的下标为0，它的左孩子下标为2 * 0 + 1；右孩子下标为2 * 0 + 2。
• 对于节点3，它存储在数组中的下标为3，它的父节点为(3 - 1) / 2

一般地，完全二叉树中一个节点在数组中的存储下标为i，则

• 左孩子为2 * i + 1
• 右孩子为2 * i + 2
• 父节点为(i - 1) / 2

堆排序

动画演示

堆排序的具体流程：

• 首先构造堆，升序构建大顶堆，降序构建小顶堆，初始堆大小即是数组长度n
• 将根节点和最后一个节点交换位置(确定了一个元素的位置)，堆大小减1
• 由于最后一个节点被换到根节点位置，堆性质可能会被破坏，因此需要调整堆

以上流程一个核心操作是调整堆，简称heapify

如上图，左边为大顶堆结构，将其根节点和最后一个节点交换后，堆大小减1，此时根节点破坏了大顶堆的规则，但是它的左右子树都是符合大顶堆结构的。我们需要对根节点进行堆调整。

从上到下调整堆(下沉)

由于一个节点变得比它的左右孩子都要小，因此需要将该节点下沉到合适的位置。

(绿色节点代表其没有破坏大顶堆结构，红色节点代表其破坏了大顶堆结构)

• 首先，根节点破坏了大顶堆结构，其左右子树都符合大顶堆结构
• 从当前调整节点的左右孩子中选择大的一个交换位置，变成中间那个形态，接下来可能还会继续破坏下去，这是一个下沉操作。

//size表示堆的大小
public static void heapify(int[] arr, int index, int size) {
        int left = index * 2 + 1;
        while (left < size) {
            int largest = left + 1 < size && arr[left + 1] > arr[left] ?
                           left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

由下到上调整堆(上浮)

由于向堆中插入一个节点而该节点又比它的父节点大，因此需要将该节点上浮到合适的位置。(这是构造堆的过程)

• 插入节点20后，由于它比父节点大，破坏了大顶堆结构，因此要将它上浮。

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

代码

public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int size = arr.length;
        swap(arr, 0, --size);
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int size) {
        int left = index * 2 + 1;
        while (left < size) {
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? 
                          left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

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

分析

排序算法	时间复杂度 (平均)	时间复杂度 (最坏)	时间复杂度 (最好)	空间复杂度	稳定性
堆排序					不稳定