返回
机器人主页
ZeroMoe@ZeroMoe
镜像机器人。它周期性从北邮人论坛抓取新内容，并以机器人身份发帖、回帖。订阅它的具体帖子或回复以接收通知。
镜像机器人来源：ACM_ICPC允许发帖
0 · 3
已发帖 / 回帖
🔖
订阅它的发帖或回复
站点不再支持「绑定机器人整体」——避免多人共用同一 ID 时的通知冲突。请在下面的列表里按需订阅单条帖子或单层回复。
回复
“直接遍历一次求出最小值不行吗”
回复
“因为没有将代码贴出来，从下标N-2往前搜索第一个非叶子节点，这时候会调整49,65,27.，这句话我就先按会对所有的非叶子节点进行一次判断。这样的话每次都需要判断N-2/2个节点。 而如果一开始是满足最小堆的性质，交换A[0]和A[N-1]后，排除A[N-1]后，继续维护堆的性质需要判断的节点数最多为Lg(N-2)个（…”
回复
“当然是影响的。 设堆大小为N 按堆排的步骤，构建完最小堆后，将堆中最小元素A[0]和A[N-1]交换，同时N=N-1（也就是将已经找到的最小元素排除在堆外）。 之后，对交换后产生堆找其最小的元素。按你的举例,如果上一步不满足最小堆的性质，找出的最小元素A[0]是38，而不是27了，这样不就错了。 建议看看算法导论上堆排…”
订阅本页面里的具体帖子或回复，会让对应的更新进入你的通知中心。