清除堆的时间复杂度是多少？

Question

我在Google上搜索了很多网站，他们都说“清除堆的时间复杂度是O（n log n）”。原因是：

• 交换尾节点的根成本为O（1）。
• 将“新根”交换到合适的位置花费O（级别）= O（log n）。
• 因此，删除节点（根）的成本为O（log n）。
• 因此删除所有n个节点的成本为O（n log n）。

---

我认为答案是正确的，但不正确，因为：]]

• 删除期间堆（或堆的级别）变小。
• 结果，“将新根交换到合适的位置”的成本变小。
• 上述“ O（n log n）”的原因没有体现这种改变。

创建堆的时间复杂度在here被证明为O（n）。

我倾向于认为清除堆的时间复杂度也O（n）

，因为创建和清除非常相似-都包含“将节点交换到合适的位置”和“改变堆大小”。

---

但是，当考虑清除堆的时间为O（n）时，这是一个矛盾：

• 通过创建和清除堆，可以在O（n）时间对数组进行排序。
• 排序时间复杂度的下限为O（n log n）。

---

我整天都在考虑这个问题，但仍然感到困惑。

清理堆的费用是多少？为什么？

我在Google上搜索了很多网站，他们都说“清除堆的时间复杂度为O（n log n）。”原因是：交换尾节点的根成本为O（1）。将“新根目录”交换到...

Answer 1

如您所正确观察，所花费的时间为O（（log n）+（log n-1）+ ... +（log 2）+（log 1））。这与O（log（n！））相同，也与O（n log n）相同（在许多地方都是证明，但例如：What is O(log(n!)) and O(n!) and Stirling Approximation）。