数据结构
2022-42
现有 n (n > 100000) 个数保存在一维数组 M 中，需要查找 M 中最小的 10 个数。请回答下列问题。
- 设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简述其算法思想（不需要程序实现）。
- 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。
答案
（1）维护一个含 10 个元素的大根堆 H，初始元素均为该数据类型可表示的最大值。依次扫描 M 中的每个元素 s：若 s 小于堆顶，则删除堆顶并将 s 插入堆中。扫描结束后，H 中即为最小的 10 个数。
（2）因为堆的规模恒为 10，平均时间复杂度为 O(n)，额外空间复杂度为 O(1)。