2.4.32

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

官网解答见:https://algs4.cs.princeton.edu/24pq/

如果这样的话,堆排序的只需要 ~nloglogn 次比较即可。
根据 2.3 中的证明,基于比较的排序的下界是 ~nlogn。
因此不存在这样的最小堆。
注意上题的方法不能用于下沉操作,因为我们不能预知下沉的路径。

上一题 下一题