关注
堆排序可以分为两个阶段。在堆的构造阶段,我们将原始数组重新组织安排进一个堆中;然后在下沉排序阶段,我们从堆中按顺序取出所有元素并得到排序结果。
1.堆的构造,一个有效的方法是从右到左使用sink()下沉函数构造子堆。数组的每个位置都有一个子堆的根节点,sink()对于这些子堆也适用,如果一个节点的两个子节点都已经是堆了,那么在该节点上调用sink()方法可以把他们合并成一个堆。我们可以跳过大小为1的子堆,因为大小为1的不需要sink()也就是下沉操作,有关下沉和上浮操作可以参考我写的优先队列那篇。
2.堆的排序,我们通过第一步操作构造了一个堆,在这个堆中,根节点永远是最大值的节点,所以我们把根节点的值与数组最后的值进行交换,在使用sink()下沉来维护堆的结构即可。
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
09-22 09:42
江西理工大学南昌校区 Java 牛客37185681...:马德,我感觉这是我面过最恶心的公司,一面是两个女hr,说什么实习前几个月属于试用期,试用期过了才能转成正式实习生,我***笑了,问待遇就是不说,问能不能接受全栈,沙币公司
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
- 1... HR面,到底该准备些啥(附核心问题回答思路)1.7W
- 2... 双非放弃保研,后悔爆哭8886
- 3... 如何委婉地拒绝offer7664
- 4... 除了卷大厂,还有其他出路吗。。。4804
- 5... 懂车帝二面 2025.10.11 1h32min4180
- 6... 10.12pdd笔试大鸭蛋3435
- 7... 牛牛求救🆘,不敢梭哈后端第二技能点怎么搭配3386
- 8... 10.12 拼多多技术岗笔试 第二题 求教3338
- 9... 小红书一面面经2514
- 10... #校招笔试##恒生电子#数据库没学过,第二道A出来了,第三道没A出来,后面有思路但是已经懒得写了2498
正在热议
更多
# 面包vs爱情,怎么选? #
3614次浏览 56人参与
# 职场新人体验 #
82260次浏览 587人参与
# 爱玛科技集团求职进展汇总 #
25797次浏览 191人参与
# 实习生如何通过转正 #
103687次浏览 1393人参与
# tplink提前批进度交流 #
206360次浏览 1504人参与
# 安克创新求职进展汇总 #
53310次浏览 527人参与
# 深信服秋招来了 #
279115次浏览 2915人参与
# Tplink求职进展汇总 #
179650次浏览 911人参与
# 秋招结束之后的日子 #
85486次浏览 975人参与
# 面试被问“你的缺点是什么?”怎么答 #
153629次浏览 2101人参与
# Offer比较,你最看重什么? #
214433次浏览 1385人参与
# 贝壳求职进展汇总 #
33715次浏览 183人参与
# 互联网公司爆料 #
144156次浏览 708人参与
# 硬件/芯片公司岗位评价 #
7752次浏览 28人参与
# 招银网络求职进展汇总 #
166370次浏览 987人参与
# 联影求职进展汇总 #
42496次浏览 282人参与
# 华为海思工作体验 #
28562次浏览 119人参与
# 新凯来求职进展汇总 #
48754次浏览 125人参与
# 五一之后,实习真的很难找吗? #
87597次浏览 556人参与
# 应届生,你找到工作了吗 #
68476次浏览 458人参与
# 26届秋招投递记录 #
48658次浏览 499人参与
# 材料进Fab厂真的劝退吗? #
55654次浏览 204人参与