排序算法：堆排序的实现和时间复杂度分析

前置知识

堆排序是将数组看成了一个二叉树，并且是一个完全二叉树，再进行排序

所以得知道完全二叉树的一些性质：设完全二叉树的层次为k，完全二叉树的节点数量在两种情况之间

• 节点数量最大为2^k - 1，最后一层的节点是满的，有2^k-1个节点
• 节点数量最小为2^k-1，最后一层只有一个节点

除了最后一层外，第i层的节点数量永远是2^i-1个。

以数组的下标当做节点的序号，即下标为i的元素对应二叉树的第i-1个节点，左右两个孩子的下标分别是(2*i+1)和（2*i+2）

• 数组下标从1开始的话，下标i对应第i个节点,并且左右孩子的下标是2*i和2*i+1

设计思路

对于一个无序的完全二叉树，排序的思路是先得到最小的元素a，再将a从二叉树删除，再得到二叉树的最小元素b，依次得到有序的所有元素

首先，需要进行建成一个最小堆（最大堆）：从最后一个父节点（非叶子节点）开始，下沉所有父节点

• 最大堆：所有父节点的值比左右孩子大
• 最小堆：所有父节点的值比左右孩子小
• 下沉：父节点的值a，与左右孩子的值进行比较，不满足堆的定义就交换，交换后值为a的节点（不为叶子节点的话）作为父节点继续下沉，与它的孩子节点交换

遍历数组，所有父节点下沉完毕，第一个元素（堆顶节点）node1就是数组的最小（大）值

 要得到所有排好序的元素，需要将元素一个个取出。首先取出node1：与堆的最后一个节点node2交换位置，然后从堆中删除node1

• 为了保持完全二叉树的性质，所以将元素放到最后一个节点再删除
• 删除不是从数组中删除，只是不将它看做二叉树的一部分

删除node1后，node2就是第一个节点，然后将node2下沉，因为当前只有node2节点不满足堆的定义，下沉后又恢复成堆，又可以取出第一个节点

从堆中不断取出第一个节点，一直到堆为空，陆续取出的节点便是排好序的数组

代码实现

通过构建大根堆，再不断取出堆顶节点到数组尾部，实现从小到大的排序

 父节点下沉的方式有循环和递归两种，在循环下沉中没有交换，而是使用了单向赋值，有一定的优化效果

import 域名ys;
import 域名om;

public class HeadSort {
    
    public static void main(String[] args) {
        //测试代码
        int[] arr = new int[20];
        for (int i = 0; i < 域名th; i++) {
            arr[i] = new Random().nextInt() % 1000;
        }
        域名tln(域名ring(arr));
        heapSort(arr);
        域名tln(域名ring(arr));
    }

    public static int[] heapSort(int[] arr) {

        // 构建最大堆
        buildHead(arr);

        // 每次将堆顶节点移到数组尾部，调整堆大小
        for (int i = 0; i < 域名th; i++) {

            // 即将要被堆删除的节点序号
            int last = 域名th - i - 1;

            swap(arr, 0, last);

            // 改变传递的len参数表示堆将节点删除
            heapify1(arr, 0, last);
        }
        return arr;
    }
    
    public static void buildHead(int[] arr) {
        int len = 域名th;
        //在满二叉树中，叶子节点数量是非叶子节点的2倍+1
        //第n-1层的最后一个节点就是len/2
        for (int i = len / 2; i >= 0; i--) {
            heapify1(arr, i, len);
        }
    }
    
    //递归下沉方式
    public static void heapify1(int[] arr, int parentIndex, int len) {
        // 左右孩子节点
        int left = 2 * parentIndex + 1;
        int right = 2 * parentIndex + 2;
        // 该父节点没有左孩子
        if (left >= len) {
            return;
        }
        int latest = left;
        /*
        将节点进行下沉，如果进行了交换，还得继续下沉，一直到成为叶子节点
         */
        // 得出左右孩子中的最大值
        if (right < len && arr[right] > arr[left]) {
            latest = right;
        }
        if (arr[latest] > arr[parentIndex]) {
            swap(arr, parentIndex, latest);
            heapify1(arr, latest, len);
        }
    }

    //循环下沉方式
    public static void heapify2(int[] arr, int parentIndex, int len) {

        //先将父节点值保存下来，跟左右的孩子比较，如果大于，跳出循环，如果小于，进行交换
        //交换之后节点继续下沉，一直到成为叶子节点
        int tmp = arr[parentIndex];
        int children = 2 * parentIndex + 1;
        while (children < len) {

            // 左孩子大于右孩子，用左孩子的值与父节点比较
            if (children + 1 < len && arr[children + 1] > arr[children]) {
                children++;
            }

            /*
            父节点大于孩子的值，不用交换
            使用的是tmp，而不是arr[parentIndex]，因为一直是单向赋值，没有交换
            直到确认tmp属于哪个节点，在循环外面将tmp赋值
             */
            if (tmp >= arr[children]) {
                break;
            }

            // 将孩子节点的值赋给父节点，孩子节点暂时不变
            arr[parentIndex] = arr[children];
            parentIndex = children;
            children = children * 2 + 1;

        }
        arr[parentIndex] = tmp;
    }

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

复杂度的计算

设数组为满二叉树来计算复杂度：树有n个节点、有k层，满二叉树的定义有：  2^k-1 = n , k = log₂(n+1)

第一阶段：构建堆，下沉所有父节点

首先在构建堆时，需要进行节点的下沉，计算最多下沉次数的时间

第k层的2^(k-1)个节点都是叶子节点，下沉0次

第k-1层的2^(k-2)个节点，下沉1次

。。。。。。

第2层的有2个节点，下沉k-2次
第1层的只有1个节点，下沉k-1次

总共下沉的时间复杂度为：s = 2^(k-2) * 1 + 2^(k-3) * 2 + ...+ 2^(1)*(k-2) + 2^(0)*(k-1)

然后使用神奇的数学知识算出这个s

首先  2s = 2^(k-1)*1 + 2^(k-2) * 2 + 2^(k-3) * 3 +.... + 2^(2)*(k-2) + 2^(1)*(k-1)

刚才的                  s =  2^(k-2) * 1 + 2^(k-3) * 2 + ... + 2^(2)*(k-3) + 2^(1)*(k-2) + 2^(0)*(k-1)

然后  2s - s = 2^(k-1) + 2^(k-2) + ... 2^(2) + 2^(1) - 2^(0)*(k-1)  = s

可以看出除了最后一项2^(0)*(k-1)外，前面k-1项一个以2位公比，2为首项的等比数列

使用等比数列求和公式：a1(1-q^n)/(1-q) ，得出 s = 2^(k) - 2 - 1*(k-1)  =  2^(k) - k - 1

又由上面的 2^(k) - 1 = n ， k = log2(n+1) 得出 时间复杂度与 数组长度n的关系：

s = n - log2(n+1)   也就是 O(n)复杂度

 第二阶段：陆续取出第一个元素，下沉新的堆顶节点

简单的看：

有n个节点需要取出，每次取出后新节点下沉 log2(n+1)，时间复杂度为  O(nlogn)

复杂的看：

二叉树每次取出一个节点后，n减1，层次k可能会变化，第i个节点下沉的次数是 log2(n-i+1)

第一个元素下沉log2(n)次，最后一个元素下沉0次，需要下沉的元素有n-1个

得到总时间为：log2(n) + log2(n-1) + .... + log2(2) = log2(n!) 

太复杂了感觉，就约等于O(nlogn)吧

所以总的时间复杂度为O(n) + O(nlogn) = O（nlogn）

循环下沉方式，空间复杂度为O(1）

使用递归下沉的话，每下沉一次都会调用一次函数，空间复杂度应该与时间复杂度一样。