树结构应用——堆排序

野性酷女 2024-03-25 23:44 31阅读 0赞

## 一、堆排序 ##

[107\_尚硅谷\_大顶堆和小顶堆图解说明\_哔哩哔哩\_bilibili][107_bilibili]

### 1.1 基本介绍 ###

*  堆排序是利用堆这种数据结构而设计的一种排序算法，**堆排序是一种选择排序**，它的最坏，最好，平均时间复杂度均为O(nlogn),它也是不稳定排序

*  **堆是具有以下性质的完全二叉树：**

每个结点的值都大于或等于其左右孩子结点的值，成为**大顶堆**

每个结点的值都小于或等于其左右孩子结点的值，称为**小顶堆**

**对左右孩子结点的值大小的比对并没有做要求**

**一般升序采用大顶堆，降序采用小顶堆**

#### 1.1.1 大顶堆举例 ####

![7a1e0957136a4a42c0ce4b0a72543071.png][]

上图大顶堆按照顺序存储可以成下方所示：

这个顺序就是按照自上往下，自左向右

![989dd492b0b2efd56ba274667fdccb4c.png][]

> **大顶堆特点：**  
> i 对应第几个节点，i从0开始编号  
> arr\[i\] >= arr\[2\*i+1\] && arr\[i\] >= arr\[2\*i+2\]

> 什么是顺序存储？ 看一看下面的文章，很简单，有公式的  
> [(31条消息) 数据结构与算法——二叉树遍历、查找、删除、顺序存储二叉树、线索化二叉树\_我爱布朗熊的博客-CSDN博客][31_ _-CSDN]

#### 1.1.2 小顶堆举例 ####

![15e2d500828dd6e83ba32261a656b3a8.png][]

**小顶堆：**

i 对应第几个节点，i从0开始编号

arr\[i\] <= arr\[2\*i+1\] && arr\[i\] <= arr\[2\*i+2\]

### 1.2 思路图解 ###

**堆排序的基本思想是:**

1.  将待排序序列构造成一个大顶堆

1.  此时，**整个序列的最大值就是堆顶的根节点。**

1.  **将其与末尾元素进行交换，此时末尾就为最大值。**

1.  然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。

1.  **此反复执行2-4**，便能得到一个有序序列了。

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

> **什么思路呢？**  
> 说白了就是不断地构建大顶堆（或者是小顶堆，升序小顶堆，降序大顶堆），然后找出最大的元素，与数组末尾(这个数组末尾是指的未发生交换的，因为在进行交换之后，数组末尾肯定比前面的都大，根本不用交换了)元素交换，末尾就是最大值，一直这样重复进行。  
> **值得注意的是，我们的堆排序并没有创建树**

**示例：**

> [108\_尚硅谷\_堆排序的思路图解\_哔哩哔哩\_bilibili][108_bilibili]

#### 1.2.1 步骤1 构造大顶堆 ####

1.  **原始数组 \[4,6,8,5,9\]**

![289c07691379dc73b3f38513cdae2332.png][]

1.  **此时我们从最后一个非叶子结点开始(叶结点自然不用调整，****第一个非叶子结点arr.length/2-1=5/2-1=1,也就是下面的6结点，arr.length/2-1此公式为计算一共有几个非叶子结点)****，从左至右，从下至上进行调整**

比如下面我们找到了第一个非叶子结点6，然后将其与左子结点和右子结点比对，即从\[6,5,9\]中找出最大的，最大的为9结点，故9结点和6结点进行交换

![42f190a2aac36ebb1f65b4c97c12818b.png][]

1.   **继续找非叶子结点，也就是4结点，由于\[4,9,8\]中9元素最大，故4和9进行交换**

![dcde77c0338d3fc0100c2b5b9dfa2976.png][]

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

![95f1f81076c72f3c2693789c341fabe8.png][]

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

> 那8结点为什么不调整呢？  
> 因为8不是一个非叶子结点

#### 1.2.2 步骤2 ####

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

将最大的元素9放到数组的末尾，再重新构建堆

![1bcf677b174469cc87d5f32e5581a886.png][]

![16d4dc84c85328f981a094a2f50d5035.png][]

**将数组最大的元素8再次放到末尾**

![f6a6d2dfe6bb4cb68426ed25716200b1.png][]

![7217a12b8f1f3d11fea087590c2e0da4.png][]

### 1.3 代码实现 ###

public class HeapSort {
        public static void main(String[] args) {
    //      要求：将数组进行升序排序，所以堆排序在这里是大顶堆排序
            int arr[] ={4,6,8,5,9};
    
            heapSort(arr);
        }
    
    
        /**
         * 编写一个堆排序的方法，大顶堆
         * @param arr
         */
        public static void heapSort(int arr[]){
            System.out.println("堆排序");
            int temp =0;
    //      1.构建堆
    //         arr.length/2-1 计算一共有几个非叶子结点
            for(int i = arr.length/2-1; i>=0;i--){
                adjustHeap(arr,i, arr.length);
            }
    
    //      2.将堆顶元素与末尾元素交换，将最大的元素沉到数组末端，
    //      3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序
            for (int j=arr.length-1 ; j>0 ; j--){
                 temp =arr[j];
                 arr[j]=arr[0];
                 arr[0]=temp;
                adjustHeap(arr,0, j);
            }
            System.out.println(Arrays.toString(arr));
        }
    
        /**
         * 功能： 完成将以i对应的非叶子结点的树调整成大顶堆
         * 如：arr[] ={4,6,8,5,9}; 变成{4,,9,8,5,6},如果再次调用这个方法，数组就变成了{4,9,8,5,6}
         * 将一个数组(对应二叉树)，调整成一个二叉树
         * @param arr    待调整的数组
         * @param i      非叶子结点在数组中的索引
         * @param length 表示对多少个元素进行调整，这个是在逐渐的减少的
         */
        public static void  adjustHeap(int arr[],int i,int length){
    //      将非叶子结点的索引对应的值保存在临时变量中
    //        临时指针保存非叶子结点的值
            int temp =arr[i];
    //      开始调整
    //          k=2*i+1  表示左子结点
    //          k=2*k+1  左边的k是右边的k的左子节点，我们把这个公式拆分一下就可以了   k1=2*i+1 ， k2=2*k1+1  这么看会不会好理解一点
            for(int k=2*i+1; k<length ; k=2*k+1){
    //             左子结点的数值比右子结点值小
                   if (k+1 <length && arr[k]<arr[k+1]){
    //                    将k指向右子节点
                          k++ ;
                   }
    //             子节点大于父节点的时候，进行处理(局部)，将大的给temp临时指针
                   if(arr[k] >temp){
                       arr[i] = arr[k];
    //                 为了下一步找他的子节点
                       i=k;
                   }else {
    //                 为什么是break呢？
                       break;
                   }
            }
    //        当for循环结束后，我们已经将i结点为父结点的树的最大值，放在了i原先的位置
    //         将非叶子结点的值赋值给与其交换的地方
            arr[i] = temp;  // 将temp值放到调整后的位置
        }
    }

[107_bilibili]: https://www.bilibili.com/video/BV1E4411H73v?p=107&vd_source=c01240addcba226237f3c4781490fbae
[7a1e0957136a4a42c0ce4b0a72543071.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ed8ef4d7e6264667bac34c0fa61edd2f.png
[989dd492b0b2efd56ba274667fdccb4c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/94c5f2a1315f4aa8afd8bc7d23c1531f.png
[31_ _-CSDN]: https://blog.csdn.net/weixin_51351637/article/details/129422343
[15e2d500828dd6e83ba32261a656b3a8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/865058e527fb4c69b12b7f199edc1ffd.png
[108_bilibili]: https://www.bilibili.com/video/BV1E4411H73v?p=108&spm_id_from=pageDriver&vd_source=c01240addcba226237f3c4781490fbae
[289c07691379dc73b3f38513cdae2332.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c80d590b1ad145468c504d60f8a882b2.png
[42f190a2aac36ebb1f65b4c97c12818b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1b5b4c45c53e4b5cbe45f7cf1296b9e4.png
[dcde77c0338d3fc0100c2b5b9dfa2976.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/75ed404bdc6b46c98945a5470a9a3857.png
[95f1f81076c72f3c2693789c341fabe8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/580c92f8f5a747eb84ec19cd905e262a.png
[1bcf677b174469cc87d5f32e5581a886.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8004ad3944da443691d1a3f5b2b845fd.png
[16d4dc84c85328f981a094a2f50d5035.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/853483c66854418ea1e846bc9874f6c1.png
[f6a6d2dfe6bb4cb68426ed25716200b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/632612e31ea145bba3b7d34538f86f34.png
[7217a12b8f1f3d11fea087590c2e0da4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/60721983886c498fb1870d205d7758ba.png