原创不易如果你觉得对你有用,哪怕一点点也好请留下一个赞再走,谢谢啦啦啦!!
- 堆排序是对于完全二叉树而言
- 定义:对于一个树高为h的二叉树如果其第0层至第h-1层的節点都满。如果最下面一层节点不满则所有的节点在左边的连续排列,空位都在右边这样的二叉树就是一棵完全二叉树(不理解没关系,是我的错不许喷我)
- 性质:如果n个节点的完全二叉树的节点按照层次并按从左到右的顺序从0开始编号,对于每个节点都有:
- 序号为0嘚节点是根对于i>0
- 其父节点的编号为(i-1)/2。
- 若2·i+1<n其左子节点的序号为2·i+1,否则没有左子节点
- 若2·i+2<n其右子节点的序号为2·i+2,否则没有右子节點
是不是很枯燥?是不是看不下去小伙子,别着急磨刀不误砍柴工。我给你上个图,你就懂上面所说的一切了
2. 那堆又是什么呢?
- 每个非叶子结点的值都大于或等于其左孩子和右孩子结点的值称之为大根堆
- 每个结点的值都小于或等于其左孩子和右孩子结点的值,稱之为小根堆
千言万语不胜一图看图哈
二、堆如何跟排序挂上钩的?
理由很简单因为堆这种数据结构可以用于排序(虽然感觉是废话,哈哈哈哈不管了,先说人话)不信你往下看
- 根据大顶堆的特性,我们可以知道大根堆的根节点就是所有节点的最大值
- 所以我们可以將最大值的根节点取下(人话:替换)与最后一个节点的值进行互换然后将剩余的节点继续构造成大根堆
非常重要呀呀呀,不懂也没关系下面有图有真相
-
首先将待排序的数组构造成一个大根堆,此时整个数组的最大值就是堆结构的顶端(根节点)
-
将顶端的数与末尾的數交换,此时末尾的数为最大值,剩余待排序数组个数为n-1
-
将剩余的n-1个数再构造成大根堆再将顶端数与n-1位置的数交换,如此反复执行便能得到有序数组
四、如何进行堆排序(附亲手画的图)
上面说的是不是还是很懵逼??没关系,既然是说人话那我就上个图来解釋:
说明:以下画的树必须满足完全二叉树,因为这是堆这个数据结构的前提
- 给定一个数组如何知道非哪些元素是非叶子节点个数呢?
- 順序是从上往下、从右往左
- 给定一个待排序的数组我们要将它变成大顶堆数组,这里之所以要给出完全二叉树来是因为这样便于理解囧
- 我们是直接操作数组使其变成大顶堆,而不是树但是原理是一样的,因为我们操作数组的时候就是用到上面说的完全二叉树的性质(下標索引找孩子节点)
- 这里用树来演示就是为了便于理解,真正操作是对数组直接操作
仔细品,不懂可以留言交流呀!图丑也欢迎留言噴哈哈哈
调整好大顶堆后根(arry[0])节点值跟倒二节点(arry[5])值又互换,看图
五、撸代码(详细注释不怕你看不懂)
纸上得来终且浅,得知此时偠躬行,看了再多还是得撸代码
如果你看到这里了要个赞不过分吧,哈哈哈哈
六、 八千万数据测试堆排序性能
上图程序中我用8千万的数據进行堆排序,我的电脑用时:
- 可能我的电脑配置比较差劲但是比冒泡、简单排序好太多了,不信你自己玩玩我这破电脑就不试了哈
- 歡迎留言看看你的运行时间是多少,看是不是吊打我电脑呢哈哈哈哈哈
- 看在我熬夜肝图的份上就点个赞吧,图不好也可以喷哈哈哈
都已經看到这了再不给赞,那就说不过去了吧
最后有兴趣一起交流的可以关注我的公众号:这里你能够学到很实用的技巧,不是常用的我鈈说公众号回复提取码即可获取以下学习资料啦啦啦啦,喜欢就拿去吧!!
(链接时常会失效若出现此类情况,可以加我微信:(加時请备注:学习资料))
-
Java web从入门到精通电子书
-
Python机器学习电子书
-
Java300集(入门、精通)
-
Java后端培训机构录集(同事培训内部提供)
-
java重要知识pdf文档(價值连城呀呀不收藏你会后悔的)
这是分享生活、电影、资料、书籍的一个公众号,有需要的也可以看看哟!