支持Insert和Extract-Min的n元素堆的时间复杂度问题咨询

给定一个包含n个元素、支持Insert和Extract-Min操作的最小堆，请问以下哪些任务可以在O(logn)时间内完成？

• 查找堆中存储元素的中位数。
• 查找堆中存储的第五小元素。
• 查找堆中存储的最大元素。
• 查找堆中存储元素的中位数。

疑问 #

1. 为什么“查找堆中存储的最大元素”不正确？我的理解是可以用O(logn)时间到达堆的底层，其中必有最大元素。
2. “查找堆中存储的第五小元素”应该是常数时间吧？因为最多只需遍历5层。
3. “查找堆中存储元素的中位数”应该需要O(n)时间？因为要通过Extract-Min取出所有n个元素得到有序数组，再用O(1)时间找中位数。

解答 #

1. 关于查找最大元素 #

最小堆仅保证父节点小于等于子节点，最大元素确实在叶子节点中，但叶子节点的数量是O(n)级别的（约n/2个）。你能以O(logn)时间到达堆的底层，但要找到最大元素必须遍历所有叶子节点，这需要O(n)时间，远超过O(logn)，因此该任务无法在O(logn)内完成。

2. 关于查找第五小元素 #

没错，这个任务可以在常数时间内完成，自然也满足O(logn)的时间要求（常数复杂度是比logn更低的量级）。最小堆的第k小元素一定存在于堆的前k层中，第五小元素最多在第5层，该层最多有2⁴=16个节点，遍历这些节点找到最小值的时间是O(1)，属于O(logn)范畴。

3. 关于查找中位数 #

你的理解是对的。中位数的位置取决于n的大小，要确定中位数至少需要知道一半元素的大小。如果依赖最小堆的Extract-Min操作，需要取出至少⌈n/2⌉个元素才能定位中位数，这部分操作的时间复杂度是O(n logn)；即使遍历整个堆收集元素再排序，时间复杂度也是O(n logn)。总之，该任务无法在O(logn)时间内完成。

内容的提问来源于stack exchange，提问作者Jack Duan