我在谷歌上搜索了很多网站，他们都说"清除堆的时间复杂度是O(n log n("。原因是：
- 交换尾矿节点根的成本为O(1(。
- 将"新根"交换到合适的位置的成本 O(level( = O(log n(。
- 因此，删除节点(根(的成本为 O(log n(。
- 因此，删除所有 n 个节点的成本为 O(n log n(。
在我看来，答案是正确的，但不"紧"，因为：
- 堆(或其级别(在删除过程中变小。
- 结果，"将新根交换到合适的位置"的成本变得更小。
- 上述"O(n log n("的原因并不体现这种变化。
创建堆的时间复杂度在这里被证明为 O(n(。
我倾向于认为清除堆的时间复杂度也是O(n(，因为创建和清除非常相似 - 两者都包含"将节点交换到合适的位置"和"堆大小的变化"。
但是，在考虑清除堆的 O(n( 时间时，这里有一个矛盾：
- 通过创建和清除堆，可以在 O(n( 时间内对数组进行排序。
- 排序的时间复杂度下限为 O(n log n(。
我已经想了一整天的问题，但仍然感到困惑。
清理一堆到底要花多少钱？为什么？
正如您正确观察到的那样，所花费的时间是 O((log n( + (log n-1( + ... + (log 2( + (log 1((。这与O(log(n！(相同(，O(n log n(相同(在许多地方证明，但例如：什么是O(log(n！((和O(n！(和斯特林近似(。
所以你是对的，关于删除堆的每个元素的时间复杂度的论点是错误的，但结果仍然是正确的。
您在创建和"清除"堆之间的等效性是错误的。当你创建堆时，有很多松弛，因为堆不变性允许在每个级别上有很多选择，这恰好意味着可以在 O(n( 时间内找到元素的有效顺序。当"清除"堆时，没有这样的松弛(关于比较排序的标准证明至少需要 n log n 时间证明这是不可能的(。