如何以O(N log k)时间构建最大堆及优化堆排序至该复杂度

常规堆排序的时间是O(N log N)，因为它要完成全量元素的排序——但你只需要最大的k个元素，完全没必要做全量排序，这就是优化的核心。

给你两种实用的调整方案：

方案一：基于最小堆的Top K筛选（推荐，严格O(N log k)） #

就是第一个问题里的思路，把筛选和后续的堆转换结合起来：

• 先用最小堆筛选出最大的k个元素（O(N log k)时间）
• 把这个最小堆转换成最大堆（O(k)时间）
• 如果需要按从大到小输出这k个元素，只需弹出堆顶k次，每次堆化O(log k)，总时间仍为O(N log k)

伪代码示例：

def get_top_k_sorted(arr, k):
    if k <= 0 or not arr:
        return []
    # 初始化最小堆
    min_heap = arr[:k]
    build_min_heap(min_heap)
    # 遍历剩余元素筛选Top K
    for num in arr[k:]:
        if num > min_heap[0]:
            min_heap[0] = num
            min_heapify(min_heap, 0)
    # 转换为最大堆，方便按从大到小输出
    build_max_heap(min_heap)
    # 弹出堆顶得到排序结果
    result = []
    for _ in range(k):
        result.append(min_heap[0])
        min_heap[0] = min_heap[-1]
        min_heap.pop()
        max_heapify(min_heap, 0)
    return result

方案二：优化全量最大堆的弹出过程（适合k接近N的场景） #

如果你已经有了一个全量最大堆（构建时间O(N)），无需重新筛选，只需弹出堆顶k次：每次弹出堆顶后，把堆的最后一个元素移到堆顶，再做一次堆化（O(log N)）。这种方法时间是O(N + k log N)，如果k远小于N（比如k是常数），时间接近O(N)，但如果k和N量级相近，还是会退化为O(N log N)，不如方案一高效。

方案一能做到严格O(N log k)的核心，是我们只维护了大小为k的堆，每次堆化的成本是log k而非log N，这才把整体时间压到了目标复杂度。

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