Получение значений с помощью 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 на самом деле 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