堆和堆排序

柔光的暖阳◎ 2021-10-19 21:12 304阅读 0赞

## 堆排序 ##

#### 堆排序基本介绍 ####

1.  堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复

杂度均为 **O(nlogn)**，它也是不稳定排序。

1.  堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有

要求结点的左孩子的值和右孩子的值的大小关系。

1.  每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
2.  一般升序采用大顶堆，降序采用小顶堆

#### 堆排序基本思想 ####

堆排序的基本思想是：

1.  将待排序序列构造成一个大顶堆
2.  此时，整个序列的最大值就是堆顶的根节点。
3.  将其与末尾元素进行交换，此时末尾就为最大值。
4.  然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序

序列了。

可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.

**步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。**

1) .假设给定无序序列结构如下

![1460404-20190610091444668-643179176.png][]

2) .此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

![1460404-20190610091455813-1849450057.png][]

3) .找到第二个非叶节点4，由于\[4,9,8\]中9元素最大，4和9交换。

![1460404-20190610091503445-300948379.png][]

4) 这时，交换导致了子根\[4,5,6\]结构混乱，继续调整，\[4,5,6\]中6最大，交换4和6。

![1460404-20190610091512318-579944853.png][]

此时，我们就将一个无序序列构造成了一个大顶堆。

**步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。**

1) .将堆顶元素9和末尾元素4进行交换

![1460404-20190610091552355-214758348.png][]

2) .重新调整结构，使其继续满足堆定义

![1460404-20190610091558940-1936820556.png][]

3) .再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

![1460404-20190610091607521-175663475.png][]

4) 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

![1460404-20190610091614516-206057328.png][]

**再简单总结下堆排序的基本思路：**

1).将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

** 代码实现**

package com.kyrie.tree;
    
    import java.util.Arrays;
    
    //要求将数组升序排序
    public class HeapSort {
    
        public static void main(String[] args) {
            int[] arr = { 4, 6, 8, 5, 9 };
            heapSort(arr);
    
        }
    
        // 堆排序
        public static void heapSort(int[] arr) {
            int tmp;
            // 第一次先找好一个最大值放到第一个位置(下标为0),实际上是先构造好一个大顶堆
            // 实际上这一步 我感觉就像是为下面的代码做的预处理似的
            for (int i = arr.length / 2 - 1; i >= 0; i--) {
                adjustToBigTopReactor(arr, i, arr.length);
            }
    
            // 将大顶堆堆顶元素 沉到 最后，然后每一次循环，我们需要构建堆的元素个数随之减一
            for (int j = arr.length - 1; j > 0; j--) {
                // 交换已经构建好的大顶堆中 堆顶 与 最后一个下标的元素 的位置
                tmp = arr[j];
                arr[j] = arr[0];// arr[0]:堆顶元素
                arr[0] = tmp;
                // 继续构建大顶堆
                // 每次从 首索引 开始往下构造，这。。。。
                adjustToBigTopReactor(arr, 0, j);
            }
            // 打印
            System.out.println("堆排序~~");
            System.out.println("数组 = " + Arrays.toString(arr));
        }
    
        // 将一个数组(一个堆的实际存储形式),调整成一个大顶堆
        /**
         * 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆..... 举例 int arr[] = {4, 6, 8, 5, 9}; => i = 1
         * => adjustHeap => 得到 {4, 9, 8, 5, 6} ,如果我们再次调用 adjustHeap 传入的是 i = 0 => 得到 {4,
         * 9, 8, 5, 6} => {9,6,8,5, 4}
         * 
         * @param arr    待调整的数组
         * @param pos    表示非叶子结点在数组中的索引
         * @param length 表示对多少个元素继续调整 ， length 是在逐渐的减少
         * @Date 2019年6月9日
         */
        public static void adjustToBigTopReactor(int[] arr, int pos, int length) {
            int tmp = arr[pos];// 先取出当前非叶子节点元素的值，保存在临时变量
            // 开始调整
            // 1. k = pos * 2 + 1 , k 是 pos 结点的左子结点
            for (int k = pos * 2 + 1; k < length; k = k * 2 + 1) {
                if (k + 1 < length && arr[k] < arr[k + 1]) {
        // 说明左子结点的值小于右子结点的值
                    k++;// k 指向右子结点
                }
                if (arr[k] > tmp) {
        // 如果子结点大于父结点
                    arr[pos] = arr[k];// 把较大的值赋给一开始的那个pos结点
                    pos = k;// !!! pos 指向 k,继续循环比较
                } else {
                    break;// !!!
                }
            }
            // 当 for 循环结束后，我们已经将 以 pos 为父结点的这棵局部（或者全局）树的最大值，放在了 最顶(局部)
            arr[pos] = tmp;// 将 先前取出的非叶子节点 temp 的值放到调整后的位置 , pos已经调整为k
        }
    
    }

转载于:https://www.cnblogs.com/kyrie211/p/10994798.html

[1460404-20190610091444668-643179176.png]: /images/20211019/34cb1fe2375a422c95f84a27b1fc0144.png
[1460404-20190610091455813-1849450057.png]: /images/20211019/033e39067a98456885084e6f6bd198a6.png
[1460404-20190610091503445-300948379.png]: /images/20211019/4c6e542323124b2a905f75dd567d1626.png
[1460404-20190610091512318-579944853.png]: /images/20211019/8214ab118cb04045bc487db5ad723957.png
[1460404-20190610091552355-214758348.png]: /images/20211019/143d19852b904b7385251c32120ed218.png
[1460404-20190610091558940-1936820556.png]: /images/20211019/3e193a72331d47179a03f734d033e2ff.png
[1460404-20190610091607521-175663475.png]: /images/20211019/36c665c2e00647538c3e31cadd91a062.png
[1460404-20190610091614516-206057328.png]: /images/20211019/c1288dc6ca904485825e3a74cc57daa5.png