堆排序及其复杂度分析

堆排序及其复杂度分析

以升序排序为例，大顶堆实现：

package leetcode.sort.compare.select;

import java.util.Arrays;

public class HeapSort {

    public void downAdjust(int[] array, int parentIndex, int length) {
        int largestIndex = parentIndex;
        int lChildIndex = 2 * parentIndex + 1;
        int rChildIndex = lChildIndex + 1;
        if (lChildIndex < length && array[largestIndex] < array[lChildIndex]) {
            largestIndex = lChildIndex;
        }
        if (rChildIndex < length && array[largestIndex] < array[rChildIndex]){
            largestIndex = rChildIndex;
        }

        // 父节点不是最大的，将最大节点和父节点交换
        if (largestIndex != parentIndex) {
            int temp = array[parentIndex];
            array[parentIndex] = array[largestIndex];
            array[largestIndex] = temp;

            // ！！！交换后可能会影响子树大小关系，递归使子树符合大顶堆规则
            downAdjust(array, largestIndex, length);
        }
    }

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

        // 1.建堆 总时间复杂度：O(n)，见分析
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            heapSort.downAdjust(array, i, array.length);
        }
        System.out.println(Arrays.toString(array));

        // 2.删除根节点（堆顶）
        for (int i = array.length - 1; i > 0; i--) {
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            heapSort.downAdjust(array, 0, i);
        }
        System.out.println(Arrays.toString(array));
    }
}

一.建堆时间复杂度分析

关键词：等差-等比数列求和，错位相减法，等比数列求和公式。

首先设置研究这个问题的前置条件：

假设目标堆是一个满堆，即第 k 层节点数为 2ᵏ。输入数组规模为 n, 堆的高度为 h, 那么 n 与 h 之间满足 n=2ʰ⁺¹ - 1，可化为 h=log₂(n+1) - 1。 (层数 k 和高度 h 均从 0 开始，即只有根节点的堆高度为0，空堆高度为 -1)。

建堆过程中每个节点需要一次下滤 *** 作，交换的次数等于该节点到叶节点的深度。那么每一层中所有节点的交换次数为节点个数乘以叶节点到该节点的深度（如第0层的交换次数为 2⁰ · h，第1层的交换次数为 2¹ · (h-1)，如此类推）。从堆顶到最后一层的交换次数 Sn 进行求和：

Sn = 2⁰ · h + 2¹ · (h - 1) + 2² · (h - 2) + ...... + 2ʰ⁻² · 2 + 2ʰ⁻¹ · 1 + 2ʰ · 0

把首尾两个元素简化，记为①式：

① Sn = h + 2¹ · (h - 1) + 2² · (h - 2) + ...... + 2ʰ⁻² · 2 + 2ʰ⁻¹

对①等于号左右两边乘以2，记为②式：

② 2Sn = 2¹ · h + 2² · (h - 1) + 2³ · (h - 2) + ...... + 2ʰ⁻¹ · 2 + 2ʰ

那么用②式减去①式，（即错位相减法）：

 得③式： Sn = -h + 2¹ + 2² + 2³ + ...... + 2ʰ⁻¹ + 2ʰ

等比数列，a1=2, q=2，使用等比数列求和公式，则③式化简为④式：

④ Sn = 2ʰ⁺¹ - (h + 2)

在前置条件中已得到堆的节点数 n 与高度 h 满足条件 n=2ʰ⁺¹ - 1（即 2ʰ⁺¹=n+1） 和 h=log₂(n+1) - 1，分别代入④式中的 2ʰ⁺¹ 和 h，化简后为：

Sn = n - log₂(n + 1)，因此最终可得渐进复杂度为 O(n).

二.删除堆顶时间复杂度

需要下沉的根节点个数：n - 1；

节点下沉交换最大次数：logn；

所以删除堆顶时间复杂度为：O(nlogn)；

综上所述：堆排序的时间复杂度为O(nlogn)