python - 理解 heapq push pop

Question

我的目标是按前十名的值对字典进行排序。使用堆似乎很合适。所以我阅读了pythons heapq并写了这个：

def top_ten_hash_tags(ranked_hash_tags):
    desc_hash_tags = []
    for hash_tag, rank in ranked_hash_tags.items():
        heapq.heappush(desc_hash_tags, (rank, hash_tag))
    top_ten = desc_hash_tags[0:10]
    while top_ten:
        i = heapq.heappop(top_ten)
        rank, hash_tag = i[0], i[1]
        print hash_tag.encode('utf-8'), (rank *-1.0)

它给出了几乎正确的结果，实际上如此接近以至于我没有注意到它是错误的。

过了一会儿，我用一些借来的代码对其进行了测试：

sorted_tags = sorted(ranked_hash_tags.iteritems(), key=operator.itemgetter(1), reverse=True)
for i in sorted_tags[0:10]:
    print i[0].encode('utf-8'), i[1]

并注意到我的错误。那么我的原始代码出了什么问题？

Answer 1

堆中的前 10 个条目并不总是包含 10 个最低的键。要获得最低的 10 个，您必须从（整个）堆中弹出 10 次。

（如果前 N 个条目始终包含 N 个最低的条目，那么您将拥有一个排序列表，而不是堆！）

一般来说，不要使用 heapq 函数以外的任何东西来修改代表你的堆的列表。