使用大小为k的最小堆查找第k小元素的时间复杂度及疑问

1. 使用大小为k的最小堆解决该问题是否正确？ #

不正确。
要找无序数组的第k小元素，核心是定位当前遍历过的元素里排名第k的值。如果用大小为k的最小堆，堆顶是堆内最小的元素，堆里存的是当前遇到的最小k个元素——这时候堆顶是第1小的元素，根本不是我们要的第k小。你没法直接从这个堆里拿到目标值，除非把堆里所有元素都取出来排序，完全浪费了堆的效率优势。

正确的思路是用大小为k的最大堆：堆顶是堆内最大的元素，堆里始终存当前遍历过的最小k个元素。这样堆顶正好就是第k小的元素——因为它是这k个最小元素里最大的那个，刚好卡在第k的位置。

2. 各堆方法对应的正确时间复杂度 #

整理几种主流堆方法的时间复杂度：

• 全局最小堆（包含全部n个元素）：
  先把整个数组建成最小堆，时间复杂度是O(n)；然后连续提取最小元素k次，每次提取后调整堆结构的时间是O(logn)，总时间复杂度为 O(n + k logn)。
• 大小为k的最大堆：
  先取数组前k个元素建成最大堆，时间O(k)；接着遍历剩下的n-k个元素，每个元素如果比堆顶小，就替换堆顶并调整堆（调整时间O(logk)），总时间复杂度为 O(k + (n-k)logk)，当n远大于k时，近似为O(n logk)。
• 大小为k的最小堆：
  这种方法本身不适合解决这个问题。如果硬要反向使用（比如用它维护当前遇到的最大k个元素），逻辑上已经变成了“反向的最大堆”，时间复杂度和大小为k的最大堆一致，但这不是最小堆的常规用法，也不符合题目里“用大小为k的最小堆找第k小”的逻辑。

3. 上述选择题的正确答案是什么？ #

首先要指出：题目里“使用大小为k的最小堆查找第k小元素”的表述存在逻辑错误，因为这种方法根本没法正确找到目标值。但结合常见的算法考题设置，大概率是题目把“最大堆”误写成了“最小堆”。

如果按照修正后的“大小为k的最大堆”来选，正确答案是 a) O(n log k)。

如果严格抠题目描述的“大小为k的最小堆”，这种方法不成立，没有对应正确选项，但考试场景下优先按笔误修正后的逻辑选a。

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