0°

数据结构和算法-堆排序

内容预览:
  • 子数组A(+1 .. n)均为叶子节点,所以我们只需要自底向上遍历非叶子节...~
  • 此篇干货,版权属于原作者~
  • 】 本文由吧主分享:http://blog.csdn.net/xiaole0313 推荐文章: 【技...~

始发于微信公众号: 程序员小乐

数据结构和算法-堆排序

作者:低调小一

地址:http://blog.csdn.net/wzy_1988/article/details/8608633

上一篇中介绍了 

堆排序概述


堆排序定义

n个关键字序列k(1), k(2), …, k(n)称为堆,当且仅当该序列满足如下性质(简称为堆性质)

  • k(i) <= k(2i) && k(i) <= k(2i+1)

  • k(i) >= k(2i) && k(i) >= k(2i+1)

若将此序列所存储的向量R[1..n]看做是一颗完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

数据结构和算法-堆排序

大根堆和小根堆

  • 根结点(亦称堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆

  • 根节点(亦称堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆

堆排序特点

  • 堆排序(heap sort)是一树形选择排序

  • 在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(或最小)的记录

堆排序

堆排序推荐阅读《算法导论》,这里把算法导论里的伪代码用c语言实现,并且优化算法结构

保持堆性质(非递归c语言)

数据结构和算法-堆排序


建堆

我们采用自底向上地用MaxHeapIfy来将一个数组A变成一个大根堆。子数组A([n/2]+1 .. n)均为叶子节点,所以我们只需要自底向上遍历非叶子节点即可

数据结构和算法-堆排序

堆排序算法

数据结构和算法-堆排序


排序练习

题目

数据结构和算法-堆排序

ac代码(堆排序)

数据结构和算法-堆排序

数据结构和算法-堆排序

数据结构和算法-堆排序


大家可以可以加群和大牛们(徐宜生、张涛等)一起学习:群二维码如下所示:

  • 数据结构和算法-堆排序

  • 如果人满了,可以加我的微信,我拉你进群,我的微信二维码:


  • 数据结构和算法-堆排序


看完本文有收获?请转发分享给更多人

关注「杨守乐」,提升编程技能

数据结构和算法-堆排序

每当我看到你的点赞、评论、或打赏都会感觉特别激动和高兴,真希望正如你看我的文章一样。我们共同努力。如果您喜欢此文,感觉对您工作有帮助,预期领导会给您涨工资,不妨小额赞助一下,让我有动力继续努力。

赞助方式如下链接:

http://blog.csdn.net/xiaole0313/article/details/52333666


如果您觉得不错,请别忘了分享到您的朋友圈让更多的人看到!! 您的举手之劳,就是对我最好的支持,非常感谢!

版权声明:【我们尊重原创。此篇干货,版权属于原作者。部分文章推送时因种种原因未能与原作者联系上,若涉及版权问题,敬请原作者联系我们,立即处理。】

本文由吧主分享:http://blog.csdn.net/xiaole0313

推荐文章:


【技术群】279126311 [满]

【技术群】484572225 [未]

如果你有好的文章想和大家分享,欢迎投稿,直接向我投递文章链接即可。投稿邮箱:[email protected]

欢迎扫描关注我们的微信公众号(),不要错过每一篇干货~

一键关注我们微信公众号 


以上就是:数据结构和算法-堆排序 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论