如何高效地获取列表中的前k个最大元素？

Question

如何以最高效、优雅且符合 Python 风格的方式解决这个问题？

给定一个包含 n 个元素的列表（或集合等），我们想要得到其中前 k 大的元素。（你可以假设 k<n/2 而不失一般性，我猜）例如，如果这个列表是：

l = [9,1,6,4,2,8,3,7,5]

假设n=9，k=3，那么如何高效地检索到前三个最大值呢？返回的结果应该是[9,8,7]，顺序不限。

谢谢！ Manuel

- Manuel Araoz

---

现在基本目的已经达成，让我们开始CODE-GOLF吧？ - Pratik Deoghare

Answer 1

使用heapq模块中的nlargest函数

from heapq import nlargest
lst = [9,1,6,4,2,8,3,7,5]
nlargest(3, lst) # Gives [9,8,7]

如果你想更改排序的标准，你还可以给nlargest方法传递一个关键字参数：

from heapq import nlargest
tags = [ ("python", 30), ("ruby", 25), ("c++", 50), ("lisp", 20) ]
nlargest(2, tags, key=lambda e:e[1]) # Gives [ ("c++", 50), ("python", 30) ]

- sharjeel

---

伟大的编程语言排名 :) ) - Paul Evans

nlargest() 会按照上述示例中提到的排序顺序返回项目吗？我在文档中找不到相关说明，所以我猜测没有这样的保证。 - Vikas Prasad

好的，我刚刚读了源代码，看起来输出总是会被排序。不错！ - Vikas Prasad

Answer 2

简单的方法是对列表进行排序，然后获取最后k个元素，时间复杂度为O(n log n)。

正确的方法是使用选择算法，其运行时间为O(n + k log k)。

此外，heapq.nlargest 平均需要O(n log k)时间，这可能足够好，也可能不够好。

（如果k = O(n)，则所有3种算法具有相同的复杂度（即不必费心）。如果k = O(log n)，则Wikipedia中描述的选择算法是O(n)，而heapq.nlargest是O(n log log n)，但双对数对于大多数实际n来说已经足够"常数化"了，所以不用担心。）

- kennytm

---

从答案中的nlargest链接来看，时间复杂度似乎是O(n log(k))而不是O(k log(n))。 - Vikas Prasad

它是klogn，而不是nlogk，你对n个元素进行二分查找（O(logn)），重复k次 => O(k logn) - user12475574

Answer 3

l = [9,1,6,4,2,8,3,7,5]

sorted(l)[-k:]

- mshsayem

---

sorted(heap) -> O(n logn) 复杂度VSheapify(heap) -> O(n) + heapq.nlargest(k, heap) -> O(k logn)最好使用后一种情况 - user12475574

Answer 4

您可以使用heapq模块。

>>> from heapq import heapify, nlargest
>>> l = [9,1,6,4,2,8,3,7,5]
>>> heapify(l)
>>> nlargest(3, l)
[9, 8, 7]
>>> 

- sykora

---

我们不需要在这里进行堆化。 - garg10may

Answer 5

sorted(l, reverse=True)[:k]

- Rorick