c - 在 O(N) 中找到 m 个最小元素的数据结构？

Question

这个问题已经有答案了:

Algorithm to find k smallest numbers in array of n items (14 个回答)

已关闭 9 年前。

我正在尝试编写一个算法来返回数组中最小的“m”元素，并且返回元素必须按从小到大的顺序排列。

假设 1<=m<=sqrt(n)，其中 n 是数组的大小。

例如，如果数组为 {8,1,12,83,33,53} 并且 m 为 3，则应返回 {1,8,12}(任何形式)。

我可以用来在 O(N) 内实现此目的的最佳通用数据结构是什么？

我正在考虑使用最小堆，但是我不能总是按顺序获得返回元素。

Answer 1

自 m < sqrt(n) ，您可以按任意顺序从堆中取出元素，然后对数组进行排序。该操作的总复杂度应小于 O(N)

(O(MlogM) < O(M^2) < O(N))

编辑:在我看来，构建堆将是一个 O(NlogM) 操作，因为您必须迭代整个数组。因此，如果您认为 logM 非常小，那么这是一个可行的解决方案。

编辑2:
This link by Jim Mischel提供有关此问题解决方案的更多信息。