排序算法之堆排序

堆排序基于完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

将一维数组看做一颗完全二叉树 如数组[9,15,7,3,25,13,8,21],可以观察出以下规律

arr[i]为arr[2*i+1],arr[2*i+2]的父节点

image.png

堆的定义

最大堆父节点大于等于子节点,体现在数组中就是 arr[i] >= arr[2*i+1]&&arr[i] >= arr[2*i+2]

最小堆 父节点小于等于子节点,体现在数组中就是arr[i <= arr[2*i+1]&&arr[i] <= arr[2*i+2]

上例对应的最大堆为

image.png

堆排序是如何实现的?

假设为正序排列,将数组看做完全二叉树

1. 构建为最大堆,此时首节点arr[0]就是最大的值
2. 依次将首节点与无序最大堆的中最后一个节点交换,然后调整堆使其满足最大堆要求

这样就构建了一个从尾节点到首节点依次减小的堆,正好满足数组的正序排列要求

如何构建最大堆?

1. 从最后一个非叶节点(arr[n/2-1]])开始,提升其子节点(可能为非叶节点)中的最大值到当前节点,并将当前节点值下放的可能的最底层.
2. 对前面的非叶节点重复 1

这样就构造出了最大堆

在首节点交换后,如何调整堆?

当首节点交换后,最后一个节点已经有序,可以忽略了.此时堆中只有首节点是不符合最大堆的定义的.对首节点应用构建最大堆的步骤即可,注意要忽略掉已经有序的尾节点

算法实现

/**
 * 将一维数组看做一颗二叉树 父节点和子节点的关系为 Nk~=N2k+1,N2k+2
 * 1. 构建堆
 * 2. 调整堆
 */
public class SimpleHeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{6545,1,4456, 5, 4, 65, 63,5445};
        heapSort(arr);
        for (int n : arr) {
            System.out.println(n);
        }
    }

    private static void heapSort(int[] arr) {
        //从最后一个节点开始扫描,构建最大堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        //依次将堆顶最大值移到当前的末尾,构建有序数组
        for (int j = arr.length - 1; j > 0; j--) {
            swap(arr, 0, j);
            adjustHeap(arr, 0, j);
        }
    }

    private static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        int k = 2 * i + 1;
        int j = i;
        while (k < length) {
            if (k+1<length&&arr[k] < arr[k + 1]) {
                k = k + 1;
            }
            if (temp < arr[k]) {
                arr[j] = arr[k];
                j = k;
            }else{
                break;
            }
            k = k * 2 + 1;
        }
        arr[j] = temp;

    }

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

重建堆的时间复杂度为O(NlogN)

树的高度为k=lgN+1,从根到叶的筛选,元素比较次数至多2(k-1)次,交换记录至多k次,排序过程中的筛选次数不超过下式:

2(lg(N-1)+lg(N-2)+lg(N-3)+lg(2))<2n()lgN

建堆的时间复杂度为O(N):

---

链接：

https://www.nowcoder.com/questionTerminal/385157a6b64540c3b233bd12f8a83ee7

来源：牛客网如果从底部最后的父节点开始建堆，那么我们可以大概算一下： 假如有N个节点，那么高度为H=logN，最后一层每个父节点最多只需要下调1次，倒数第二层最多只需要下调2次，顶点最多需要下调H次，而最后一层父节点共有2^{(H-1)个,倒数第二层公有2}(H-2),顶点只有1(2^0)个，所以总共的时间复杂度为s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0 将H代入后s= 2N - 2 - log2(N)，近似的时间复杂度就是O(N)。