第 27 题:如何理解堆排序?
2021/8/20 13:05:52
本文主要是介绍第 27 题:如何理解堆排序?,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
什么是堆排序?
是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点
在看本文之前请先了解以下概念
完全二叉树:除了最后一层之外的其他每一层都被完全填充,每一层从左到右的填充数据,不能空缺(只是类似这个结构,所以本文不会用到这个知识点)
堆:分为大顶堆和小顶堆两种
大顶堆(小顶堆):可分为有序区和无序区,初始全部为无序区
执行的步骤是如何进行的?
-
无非就是将一个无序数组转化为大顶堆(小顶堆)
-
将堆顶的值和无序数组末尾值交换位置
-
根据堆的性质进行调整,成为大顶堆(小顶堆)
-
然后又继续 1~3 的步骤,反反复复直到无序区没有值为止
这个时候肯定会有人问,怎么区别有序区和无序区?什么是大顶堆(小顶堆)?以及大顶堆(小顶堆)是如何调整出来的?
如何辨别有序区和无序区?
循环结束后应该是这样的,没有无序区了
上面的大顶堆(小顶堆)实际在存储在数组中是这样的
现在应该知道有序区和无序区如何分辨了吧,以及大顶堆是如何在数组中进行存储的
什么是大顶堆(小顶堆)?
通过上图应该都能看出来大顶堆和小顶堆的区别了吧。
大顶堆:每个结点的值都大于或等于其左右孩子结点的值(大到小排列)
小顶堆:每个结点的值都小于或等于其左右孩子结点的值(小到大排列)
大顶堆(小顶堆)是如何调整出来的?
也是本文中最难理解的地方,下面简单描述一下主要的步骤:
目标:将无序数组(R1,R2…Rn)构建成大顶堆,即完成任务
-
初始时,此堆的所有值都是属于无序区
-
将堆顶元素 R[1]与无序区中最后一个元素 R[n]交换,此时得到新的无序区(R1,R2,…Rn-1)和新的有序区(Rn)
-
由于交换后新的堆顶 R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,…Rn-1)调整为新堆
-
然后再次将 R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2…Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到无序区的元素个数 0,则整个排序过程完成
总结
-
其实主要的操作就是构造初始堆和调整堆。
-
每次调整都是从父节点(i - 1)/ 2、左孩子节点(2 _ i + 1)、右孩子节点(2 _ i + 2)三者中选择最大者跟父节点进行交换位置
堆排序过程
这篇关于第 27 题:如何理解堆排序?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)