堆排序可以分为两个阶段。在堆的构造阶段,我们将原始数组重新组织安排进一个堆中;然后在下沉排序阶段,我们从堆中按顺序取出所有元素并得到排序结果。 1.堆的构造,一个有效的方法是从右到左使用sink()下沉函数构造子堆。数组的每个位置都有一个子堆的根节点,sink()对于这些子堆也适用,如果一个节点的两个子节点都已经是堆了,那么在该节点上调用sink()方法可以把他们合并成一个堆。我们可以跳过大小为1的子堆,因为大小为1的不需要sink()也就是下沉操作,有关下沉和上浮操作可以参考我写的优先队列那篇。 2.堆的排序,我们通过第一步操作构造了一个堆,在这个堆中,根节点永远是最大值的节点,所以我们把根节点的值与数组最后的值进行交换,在使用sink()下沉来维护堆的结构即可。
点赞 评论

相关推荐

牛客96763241...:杭电✌️也是打完招呼,没人回吗
点赞 评论 收藏
分享
牛客37185681...:马德,我感觉这是我面过最恶心的公司,一面是两个女hr,说什么实习前几个月属于试用期,试用期过了才能转成正式实习生,我***笑了,问待遇就是不说,问能不能接受全栈,沙币公司
如果可以选,你最想去哪家...
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务