我在网上遇到一个问题，询问从堆支持的最小优先级队列中获取最大值的平均时间复杂度。
我推断答案为 O(n)，因为堆由数组支持，迭代一次数组来查找最大值将需要 n 次比较.
但是，答案是O(nlogn)。谁能解释为什么会出现这种情况以及我的推理失败的地方吗？
最佳答案
堆可以由数组支持(如果您选择以这种方式实现)。由于大多数编程语言都有数组，因此这样做是有意义的。但从外部来看，我们不能这样认为。
是的，从技术上讲，您可以在线性时间内找到最大值如果您有权访问数组，但您不会。示例...在 Java 中，您是否可以访问 ArrayList 类后面的动态大小的数组？不，因为 Java 不希望你把它搞砸!
假设您只能使用 Heap 类公开的公共(public)方法/属性...您很可能无法访问该数组。如果该数组是公开可用的，那么它很容易被操纵，并且堆结构也很容易被破坏。
我认为这个问题假设您将使用堆的方法。在最小堆中，最大值将出现在末尾(堆排序)，这需要对 remove() 函数进行 n 次调用，即 O(logn)，因此 n * log(n) 意味着堆排序是 O(n*logn)。
简单来说，问题是问堆排序的时间复杂度。
关于java - 从堆支持的最小优先级队列获取最大值的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47762387/