堆和堆排序

一、什么是堆

​ 认识堆以前，首先要明确两个概念：满二叉树 和 完全二叉树：

​ 满二叉树：在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

​ 完全二叉树：对一棵具有 n 个节点的二叉树按层序编号，如果编号为 i 的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。

​
​ 堆：堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子节点的值，称为大顶堆；或者每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆。

二、两种构建堆的方法

2.1 bottom-top

​ 该方法的思路是把数组先全部加载到数组里，然后按照完全二叉树的结构从下往上，从右往左逐步建堆，最后把整个二叉树扩展成堆。

​ 时间复杂度分析：

​ 设有 n 个节点，则这 n 个节点构成的完全二叉树深度为 log(n)，把高度设为 h

​ 第 m 层最多的节点个数是 2^(m) ，每个节点需要下移的最多的次数是 (h - m) 次，则时间复杂度

​ T = 2^(h - 1) * 1 + 2^(h - 2) * 2 + 2^(h - 3) * 3 + … + 2^1 * (h - 1) + 2^0 * (h) （1）

等式两边同乘 2

2T=2^h * 1 + 2^(h - 1) * 2 + 2^(h - 2) * 3 + 2^(h - 3) * 4 + …+2^1 * (h) (2)

用 (2) 式减 (1) 式得

T = 2^h + 2^(h - 1) + 2^(h - 2) + … + 2^1 - 2^0 (3)

根据等比数列求和公式得

T = 2^(h + 1) - h - 1

h = log2(n)，所以得 T = n - log2(n) + 1，即时间复杂度为 O(n)

​ 代码：

void createHeap() {
        int[] arr = new int[]{54, 87, 27, 67, 19, 31, 29, 18, 32, 56, 7, 12, 31};

        int currentPos = (arr.length - 2) / 2;	//最后一个非叶子节点
        while(currentPos >= 0) {
            //调整
            filterDown(arr, currentPos, arr.length);
            currentPos--;
        }
}

//构建大根堆
void filterDown(int[] arr, int start, int end) {
    int i = start;
    int temp = arr[i];
    int j = 2 * i + 1;  //左子树
    while(j < end) {
        if(j + 1 < end) {
            j = (arr[j] > arr[j + 1]) ? j : j + 1;	//左右子女挑大的
        }

        if(temp < arr[j]) {
            arr[i] = arr[j];		//把大的子女移到上面
            i = j;
            j = 2 * i + 1;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

2.2 top-bottom

​ 该方法的思路是每次把数据插入到堆的最后一个位置，逐步把该节点往上升，直到升不动为止。

​ 时间复杂度：这种方法的时间复杂度很好分析，一共 n 个节点，每个节点最大比较 log2(n) 次，所以时间复杂度就是 n * log2(n)

void createHeap() {
    int[] arr = new int[]{54, 87, 27, 67, 19, 31, 29, 18, 32, 56, 7, 12, 31};

    //相当于是一个一个插入到堆的末尾，再向上调整成堆
    int currentPos = 0;
    while(currentPos < arr.length) {
        filterUp(arr, currentPos);
        currentPos++;
    }
    for (int i : arr) {
        System.out.print(i + " ");
    }

}

void filterUp(int[] arr, int end) {
    int i = end;
    int temp = arr[i];
    while(i >= 0) {
        int j = (i - 1) / 2;	//父节点
        if(j >= 0) {
            if(arr[i] > arr[j]) {	//如果比父节点大，父节点下沉
                arr[i] = arr[j];
                i = j;
            } else break;
        } else break;
    }

    arr[i] = temp;	//移动到最后的位置，这种方式减少了交换次数
}

2.3 两种建堆方式的对比

​ 第一种建堆方式主要用于堆元素已经确定好的情况，第二种方式主要用于动态增加元素来建堆。插入建堆的过程也常用于建立优先队列的应用。

三、堆排序

3.1 基本思想

​ 堆排序的基本思想就是把待排序的序列造成一个大顶堆。此时，整个序列最大的值就是堆顶的根节点。将它移走（为了节省空间，就直接和最后一个节点互换位置了），然后将剩余 n - 1 个节点重新构造成一个堆，这样就会得到 n 个元素中的次小值。如此反复执行，便能得到一个有序序列了（如果用了节省空间的方法，那么大根堆得到的是升序序列，小根堆得到的是降序序列）。

3.2 复杂度分析

​ 时间复杂度：

​ 共需要移走 n 个节点，每移走一个节点重新建堆需要 log(n) 的时间，所以时间复杂度为 n * log(n)

​ 空间复杂度：

​ 没有开辟额外的空间，所以是 O(1)，如果不用节省空间的方法，空间复杂度是 O(n)。

3.3 稳定性分析

​ 因为堆排序存在跳跃，所以堆排序是不稳定的（随手画一下就发现了）。

3.3 代码

void createHeap() {
        int[] arr = new int[]{54, 87, 27, 67, 19, 31, 29, 18, 32, 56, 7, 12, 31};

        int currentPos = (arr.length - 2) / 2;	//最后一个非叶子节点
        while(currentPos >= 0) {
            //调整
            filterDown(arr, currentPos, arr.length);
            currentPos--;
        }
}

//构建大根堆
void filterDown(int[] arr, int start, int end) {
    int i = start;
    int temp = arr[i];
    int j = 2 * i + 1;  //左子树
    while(j < end) {
        if(j + 1 < end) {
            j = (arr[j] > arr[j + 1]) ? j : j + 1;	//左右子女挑大的
        }

        if(temp < arr[j]) {
            arr[i] = arr[j];		//把大的子女移到上面
            i = j;
            j = 2 * i + 1;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

//只在建好的堆上加个排序方法即可
void sort(int[] arr) {
    int j = arr.length - 1;
    while(j >= 0) {
        swap(arr, 0, j);	//第一个和最后一个互换
        filterDown(arr, 0, j);	//重新建堆
        j--;
    }
}