algorithm - 从最小堆中移除的平均时间复杂度

Question

按顺序移除(即最小堆上的 removeMin)堆上所有元素的平均时间复杂度 ???

Answer 1

这个问题本质上是关于堆排序的——构建一个最小堆，然后一次删除一个元素以生成一个排序列表。构建最小堆的时间复杂度为 O(N)，而这个成本将主要由提取元素的成本决定。

堆排序提取阶段的最坏情况相对容易——每次移除是 O(log N) 并且有 N 个，因此复杂度必须是 O(N log N)。

这并不意味着平均值是 O(N log N)。为此，我们需要 Lower bound on heapsort?展示更困难的东西——即，提取阶段的最佳案例复杂度也是 Theta(N log N)。

平均值必须介于最佳 (Theta(N log N)) 和最差 (O(N log N)) 情况之间，Theta(N log N) 也是如此。