根據元組中的第一個值使用Python的heapq.nlargest（）檢索值

Question

最終，我想要的是我要做的是根據他們的分數返回前十名'項目'的列表。我試圖實現使用heapq各種各樣的優先級隊列，到目前爲止，我已經得到了什麼：

class my_queue: 
    # heap-based priority queue for top items 
    def __init__(self): 
    self.top_items = [] 

    def push_item(self, item): 
    score = item.get_score() 
    item_name = item.get_name() 
    heapq.heappush(self.top_items, (score, item_name)) 

    def top_ten(self): 
    top_ten_items = heapq.nlargest(10, self.top_items, key=lambda s: s[0]) 
    print top_ten_items 

我正在與key=lambda s: s[0]做的是試圖理清基於score從(score, item_name)堆。有沒有簡單的方法來完成這個基於我在這裏的結構？

感謝。

Answer 1

heapq.nlargest是一個等同於：

sorted(iterable, key=key, reverse=True)[:n] 

這意味着呼叫heapq.nlargest(10, self.top_items)將所有項目重新排序，你不會有任何heap數據結構的好處。

heap中的最小項可以用heapq.heappop函數調用獲得，因爲heap的python實現實際上是min heap。

要獲得n來自heap的最大項目，您需要將最大項目推到heap（乘以-1）之前最小。例如，像這樣：

class my_queue: 
    # heap-based priority queue for top items 
    def __init__(self): 
     self.top_items = [] 

    def push_item(self, item): 
     # minus to make the largest scores the smallest 
     heapq.heappush(self.top_items, (-item.get_score(), item)) 

    def top_ten(self): 
     top_ten_items = [] 
     for i in xrange(10): 
      # minus to revert minus in push_item 
      large_item = -heapq.heappop(self.top_items) 
      top_ten_items.append(large_item) 

     print top_ten_items