字典（Python）中前n个值（和键）的新dict

Question

我有一本姓名词典，以及姓名在通讯录中出现的次数：

names_dict = {
    'Adam': 100,
    'Anne': 400,
    'Britney': 321,
    'George': 645,
    'Joe': 200,
    'John': 1010,
    'Mike': 500,
    'Paul': 325,
    'Sarah': 150
}

最好不要使用sorted()，我希望遍历字典并创建一个只有前五个名称的新字典：

^{pr2}$

我似乎能够创建一个新的字典，每当我们遍历names-tu-dict并找到一个比new-dict中的值高的名称/计数时，它就会得到一个新的键/值对。但是，我不知道如何在从names-tu-dict中添加大的之后从new-dict中删除较小的

有没有更好的方法-不必导入特殊的库或使用sorted()来迭代dict并创建具有最高值的前N个键的新dict？在

Answer 1

您应该使用^{} function来实现这一点：

import heapq
from operator import itemgetter

top_names = dict(heapq.nlargest(5, names_dict.items(), key=itemgetter(1)))

这使用了一个更有效的算法（对于大小为N的dict，使用O（NlogK）和K个top items）将前5个项提取为(key, value)元组，然后将这些元组传递给dict()以创建新字典。在

演示：

^{pr2}$

您可能需要使用^{} class。^{} method会让你的用例变得很容易解决。该方法的实现在幕后使用heapq.nlargest()。在

这些是而不是特殊库，它们是Python标准库的一部分。否则，您必须自己实现一个binary heap来实现这一点。除非您专门研究这个算法，否则重新实现您自己的算法是没有意义的，Python implementation对某些关键函数使用extension written in C进行了高度优化）。在

Answer 2

我不知道，为什么您不想使用sort，而解决方案并不完美，甚至与您的问题不完全匹配，但我希望它能激励您找到自己的实现。我认为这只是你真正问题的一个简短的例子。在

但正如你在另一个答案中看到的：通常最好是使用代码，这是在以前编写的，而不是自己去做所有的事情。在

names_dict = {'Joe' : 200, 'Anne': 400, 'Mike': 500, 'John': 1010, 'Sarah': 150, 'Paul': 325, 'George' : 645, 'Adam' : 100, 'Britney': 321}

def extract_top_n(dictionary, count):
    #first step: Find the topmost values
    highest_values = []
    for k,v in dictionary.iteritems():
        print k,v, highest_values, len(highest_values)
        highest_values.append(v)
        l = len(highest_values)
        for i in range(l-1):
            print i,l
            if l-i < 1:
                break
            if highest_values[l-i-1]>highest_values[l-i-2]:
                temp = highest_values[l-i-2]
                highest_values[l-i-2] = highest_values[l-i-1]
                highest_values[l-i-1] = temp
        highest_values = highest_values [:count]

    #fill the dirctionary with all entries at least as big as the smallest of the biggest
    #but pay attention: If there are more than 2 occurances of one of the top N there will be more than N entries in the dictionary
    last_interesting = highest_values[len(highest_values)-1]
    return_dictionary = {}    
    for k,v in dictionary.iteritems():
        if v >= last_interesting:
            return_dictionary[k] = v
    return return_dictionary

print extract_top_n(names_dict,3)