java - 从堆支持的最小优先级队列获取最大值的时间复杂度

Question

我在网上遇到一个问题，询问从堆支持的最小优先级队列中获取最大值的平均时间复杂度。

我推断答案为 O(n)，因为堆由数组支持，迭代一次数组来查找最大值将需要 n 次比较.

但是，答案是O(nlogn)。谁能解释为什么会出现这种情况以及我的推理失败的地方吗？

Answer 1

堆可以由数组支持(如果您选择以这种方式实现)。由于大多数编程语言都有数组，因此这样做是有意义的。但从外部来看，我们不能这样认为。

是的，从技术上讲，您可以在线性时间内找到最大值如果您有权访问数组，但您不会。示例...在 Java 中，您是否可以访问 ArrayList 类后面的动态大小的数组？不，因为 Java 不希望你把它搞砸!

假设您只能使用 Heap 类公开的公共(public)方法/属性...您很可能无法访问该数组。如果该数组是公开可用的，那么它很容易被操纵，并且堆结构也很容易被破坏。

我认为这个问题假设您将使用堆的方法。在最小堆中，最大值将出现在末尾(堆排序)，这需要对 remove() 函数进行 n 次调用，即 O(logn)，因此 n * log(n) 意味着堆排序是 O(n*logn)。

简单来说，问题是问堆排序的时间复杂度。