倚楼听风雨
淡看江湖路

浅析数据结构之堆结构的基础知识以及堆排序

数据结构之堆结构

“堆”是一种树形结构,我们可以理解为堆是利用完全二叉树(对一颗具有n个结点的二叉树按层序编号,如果编号为i(1≤i≤n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为为完全二叉树)的结构来维护一组数据,并在实现”优先队列”时使用。

优先队列也是一种数据结构。在优先队列中,数据可以按任意顺序添加。相反,在取出数据时,首先选择最小值。能够自由地添加数据并从最小值开始取出,这种定义为优先队列。

让我们看看堆的结构。作为堆的一个规则,子类数字总是大于等于其父类数字-最小堆(或者子类总是小于等于其父类-最大堆),其实只有当堆是最大堆或者最小堆才是真正意义上的堆。从堆中取出数字时,从最上面的数字取出。在堆中,最小值保存在顶部位置。所以使用堆这种数据结构可以快速取出最小的数据,但是无法执行在树中间取出数据的操作。

数据结构之堆结构最大堆与最小堆完全二叉树表示示意图 第1张

堆用于如优先队列、戴克斯特拉算法和堆排序等。关于戴克斯特拉算法属于数据结构中的搜索查找的内容,是图表搜索的算法,老四后期会浅析,你也可以先参考一下维基百科的介绍:

数据结构”堆”的动态描述图示如下,包含堆在移除顶部元素之后如何进行重排序的介绍。感谢同事”菠菜”同学提供的参考动图。

数据结构之堆结构动画图解-高老四博客 第2张

内容来自软件算法动画图解,喜欢的请付费支持,侵删

Java模拟堆(最小堆)的基本实现代码如下:

堆排序

说到堆就离不开堆排序,但是其实再说堆的时候基本上就已经算是再讲堆排序(最大堆,最小堆)了,唯一不同的是堆排序需要我们输出一个完全有序的序列,所以在初始建堆的基础之上还需要进行堆顶与堆最后一个元素进行交换位置的操作,是简单选择排序的改进排序算法。结合上述介绍堆结构我们再来总结一下堆以及堆排序的相关知识点:

  • 堆排序是简单选择排序的改进,简单排序的代码可参考下方代码
  • 堆的性质: 每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;每个结点的值都小于等于其左右孩子结点的值,称为小顶堆;既不是大顶堆也不是小顶堆不是完整意义上的堆结构
  • 完全二叉树的特点:
    — 叶子结点只能出现在最下两层
    — 最下层的叶子一定集中在左部连续位置
    — 倒数第二层,若有叶子结点,一定都在右部连续位置
    — 如果结点度为1,则该结点只有左孩子,即不存在只有右子树的情况
    — 同样结点数的二叉树,完全二叉树的深度最小
  • 满二叉树: 在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树

  • 满二叉树的特点:
    — 叶子结点只能出现在最下一层.出现在其它层就不可能达到平衡.
    — 非叶子结点的度一定是2.否则就是缺胳膊少腿了
    — 在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多
  • 堆排序的时间复杂度: O(nlogn)

简单选择排序

通过n-i次关键字间的比较,从n-i+1个记录中选出的关键字最小的记录,并和第i(1≤i≤n)个记录交换之。简单选择排序时间复杂度: O(n²)。
使用Java描述简单选择排序代码示例如下:

堆排序动态描述图如下:

数据结构之堆排序Heap Sort动态Gif教程图解 第3张

Java描述堆排序代码如下:

说得容易,但是初学者肯定理解起来还是需要多花时间理解一下,平时再多看看一些书籍里面的详解,加深一下印象。

更博不易,如果觉得文章对你有帮助并且有能力的老铁烦请赞助盒烟钱,点我去赞助。或者扫描文章下面的微信/支付宝二维码打赏任意金额,老四这里抱拳了。赞助时请备注姓名或者昵称,因为您的署名会出现在赞赏列表页面,您的赞赏钱财也会被用于小站的服务器运维上面,再次抱拳。

赞(26) 给你买杜蕾斯
本站原创文章受自媒体平台原创保护,未经允许不得转载高老四博客 » 浅析数据结构之堆结构的基础知识以及堆排序

开始你的表演 抢沙发

觉得文章有用就打赏一下老四,鼓励我更好的创作

非常感谢你的打赏,我们将继续给力更多优质内容,让我们一起创建更加美好的网络世界!

支付宝扫一扫打赏

微信扫一扫打赏

登录

找回密码

注册