首页 > 编程语言 > 详细

算法 堆排序

时间:2021-05-26 01:02:47      阅读:53      评论:0      收藏:0      [点我收藏+]

堆排序从二叉树演化而来。

堆,分为大根堆和小根堆;

大根堆:一个特殊的完全二叉树,他的父节点一定比子节点大;

小根堆:父节点一定比子节点小;

下面的例子都是用大根堆

技术分享图片

 

 

 

有两个重点

1.堆的向下调整

  树的根节点的左右都是堆,但自己不是堆,这种时候可以通过向下调整,成为堆。

  图1,需要向下调整

技术分享图片

图2,将根节点2与它的子节点9和7比较,都比他大,将更大的往上提,2放到9的位置,继续跟8和5比较,以此类推

技术分享图片

 

 图3,最终形成堆

技术分享图片

 

 

 

2.如何构建堆

  一个无序的树,怎么构建成堆?

  图1 是一个无序的树,首先我们找到第一个非叶子节点(从后往前找),这里是3

  技术分享图片

 

  发现3的叶子节点是5,比它大,不符合大根堆条件,因此对3-5这个子树,做一个堆的向下调整操作,变成5-3

技术分享图片

 

   因为 9 这个节点 的叶子节点都比它小,所以不需要调整,我们看1这个节点,需要向下调整

  技术分享图片

 

   再看8这个节点,比9小比5大,因此调整

  技术分享图片

 

   最后调整6,也就是根节点,一个有序的堆就构建完成了。

  技术分享图片

 

算法 堆排序

原文:https://www.cnblogs.com/luyShare/p/14811499.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!