算法选择题：堆、优先队列与 Top K（5 题）
041 用数组构建二叉堆，哪种表述准确？
难度： 基础
- A. 自底向上 Heapify 与逐个插入的复杂度相同
- B. 对完整数组自底向上 Heapify 可在 O(n) 时间建堆；逐个执行 n 次入堆则是 O(n log n)
- C. 建堆完成后，堆数组一定是有序的
- D. 任何建堆方式都必然是 O(n log n)
查看答案与解析
正确答案B
正确原因： 对完整数组自底向上 Heapify 可以在 O(n) 时间建堆；逐个执行 n 次入堆则是 O(n log n)。
错误选项辨析： A 项：Heapify 是 O(n)，逐个插入是 O(n log n)，两者不同；C 项：堆只保证父与子的大小关系，不保证整体有序；D 项：自底向上 Heapify 的累加成本是 O(n)，并非所有方式都是 O(n log n)。
042 关于二叉堆的操作成本，哪种表述准确？
难度： 进阶
- A. 出堆操作通过交换堆顶与末尾实现，因此是 O(1)
- B. 堆支持 O(1) 查找任意元素，与哈希表相同
- C. 查看堆顶 O(1)，入堆与出堆通常 O(log n)；在堆中查找任意值仍可能需要 O(n)
- D. 堆中所有查询都和堆顶一样是 O(1)
查看答案与解析
正确答案C
正确原因： 查看堆顶 O(1)，入堆和出堆通常 O(log n)；在堆中查找任意值仍可能需要 O(n)。
错误选项辨析： A 项：交换是 O(1)，但随后的下沉调整是 O(log n)；B 项：堆不维护值与位置的索引，任意查找是 O(n)；D 项：只有堆顶是 O(1)，任意值查找需要遍历。
043 从 n 个元素中找最大的 K 个（K 远小于 n），哪种方案最合理？
难度： 进阶
- A. 维护大小为 K 的小根堆，时间 O(n log K)；K 接近 n 时整体排序可能更简单
- B. Top K 必须先对全部元素完整排序
- C. Top K 问题只能使用堆，其他方案都不正确
- D. 要取最大的 K 个，应维护大小为 K 的大根堆，堆顶就是第 K 大元素
查看答案与解析
正确答案A
正确原因： 维护大小为 K 的小根堆可在 O(n log k) 找最大 K 项；K 接近 n 时排序方案可能更简单。
错误选项辨析： B 项：大小为 K 的堆只需要保留 K 个候选，无需完整排序；C 项：K 接近 n 时排序更简单，分治与选择算法也是可行方案；D 项：候选堆必须用最小堆才能以 O(1) 找到可淘汰的最小候选，大根堆堆顶是最大而非第 K 大。
044 关于 .NET PriorityQueue<TElement, TPriority> 的出队顺序，哪种表述准确？
难度： 进阶
- A. PriorityQueue 默认总是最大堆，先出最大值
- B. PriorityQueue 的出队顺序与插入顺序一致（FIFO）
- C. Priority 相等时元素顺序由哈希决定，无法控制
- D. 默认优先移除 Priority 最小的元素（最小堆语义）；实现最大堆需反转优先级或使用自定义比较器
查看答案与解析
正确答案D
正确原因： PriorityQueue 默认优先移除最小 Priority；实现最大堆需反转优先级或使用自定义比较器。
错误选项辨析： A 项：.NET 默认按 Priority 升序出队，与最小堆语义一致；B 项：出队顺序由 Priority 决定，不是 FIFO；C 项：相等优先级时按插入顺序稳定出队，不涉及哈希。
045 用双堆维护数据流中位数，哪种表述准确？
难度： 综合
- A. 最大堆保存较小一半、最小堆保存较大一半；两堆大小差不超过一且所有左侧值不大于右侧值，中位数即可 O(1) 取得
- B. 把全部数据放入一个堆，堆顶就是中位数
- C. 双堆方案要求数据全部预先到达，不能流式处理
- D. 只维护两个堆的大小就能保证中位数正确
查看答案与解析
正确答案A
正确原因： 最大堆保存较小一半，最小堆保存较大一半；两堆大小差不超过一且所有左侧值不大于右侧值。
错误选项辨析： B 项：堆顶是极值而非中位数，堆也不支持按序取中位；C 项：双堆正是为流式插入设计，每插入一次做一次平衡；D 项：除了大小差，还必须保证左侧最大值不超过右侧最小值。