在字典python中找到前k个最大的键

Question

可以说我有一本字典:

{key1:value1........... keyn:valuen}

所以我想说我想写一个函数

def return_top_k(dictionary, k):

    return list_of_keys_sorted   

获得具有前k个值的键(保持顺序,即最高值键出现在开头......等等),最有效的方法(就大O而言)是多少.

Answer 1

O(n log k):

import heapq

k_keys_sorted = heapq.nlargest(k, dictionary)

您可以使用key关键字参数指定应该用作排序键的内容,例如:

k_keys_sorted_by_values = heapq.nlargest(k, dictionary, key=dictionary.get)

Answer 2

return sorted(dictionary, key=dictionary.get, reverse=True)[:10]

应该是最糟糕的O(NlogN)（尽管heapq其他人提出的建议可能更好）...

这可能也是有道理使用Counter一个普通的字典来代替。在这种情况下，该most_common方法将（大约）完成您想要的操作（dictionary.most_common(10)），但前提是要Counter在您的API中使用。