算法题求解，关于排序

[hwdef]

在百万级数据中怎么找到最大的 10 个数？

我觉得应该不会用排序，只会用标记，这么大的数据，什么排序也都太慢了。 可能是我想的太简单 不知道大家有什么想法。

[linap]

一个 10 大小的数组。遍历数据，数据如果大于数组中的最小的数，替换那个数

[twistoy]

维护一个大小为 10 的大根堆。时间复杂度 O(n)

[aaax7676]

top k 问题，维护个容量为 k 的堆

[sylxjtu]

跑 10 遍 nth_element?

[neosfung]

@twistoy 小根堆

[Win78]

优先队列

[easylee]

题目我没有什么好的解决办法，但是搁在实际应用中，我是后台定时排序，然后存储标记，这样一来虽然不能做到实时查询，但是很方便，不会牺牲时间复杂度。

[twistoy]

@neosfung 取最大的 10 个应该是大根堆吧

[neosfung]

@twistoy 小根堆，堆顶是前十个最大数中，最小的数。新进来的数和堆顶比较大小，比堆顶大的，就把堆顶换成新进来的数，然后调整堆；否则比堆顶小的，就不管了。

[hwdef]

@linap 这个方法确实很简单

[chashao]

@twistoy 我觉得时间复杂度是 O(10lgn)

[twistoy]

@chashao 怎么可能…
n 个数至少要遍历一遍，至少是 O(n)

[chashao]

@twistoy 每次建堆不是 O(lgn)么……

[twistoy]

@chashao 但是堆大小是固定 10 的

[Templ1]

静态查询-->右转各种堆，各种排序
动态查询-->平衡树