python heapq：如何使用列表列表中的第n個元素對堆進行排序？

所以我有列表被添加到堆中;例如：python heapq：如何使用列表列表中的第n個元素對堆進行排序？

n = [[1, 5, 93], 
    [2, 6, 44], 
    [4, 7, 45], 
    [6, 3, 12]] 

heapq.heapify(n) 
print(n)

根據列表的第一個元素進行比較和排序。

我的問題是，我如何排序heapq，因此它比較每個列表的第三個元素？例如，上面的列表就會從heapq順序訪問：

[[6, 3, 12], 
[2, 6, 44], 
[4, 7, 45], 
[1, 5, 93]]

來源

2017-08-26 Aditya Pokharel

'sorted（your_list_of_lists，key = lambda x：x [2]）' – DyZ

您是在尋找「排序」還是您有一些插入並刪除？ – AChampion

我不能使用其他任何東西。我對算法的時間複雜性非常緊張，所以我需要爲我節省一些大的O.有什麼辦法讓heapq本身以不同的順序存儲列表？（PS：我也編輯了這篇文章，以澄清一些事情） –

heapq不支持key功能它的排序，所以你需要操縱你的數據結構。映射列表到tuple(sort_value, list)將允許你這樣做log(n) push和pop：

In []: 
q = [(x[2], x) for x in n] 
heapq.heapify(q) 
heapq.heappop(q) 

Out[]: 
(12, [6, 3, 12]) 

In []: 
l = [2, 5, 1] 
heapq.heappush(q, (l[2], l)) 
heapq.heappop(q) 

Out[]: 
(1, [2, 5, 1])

另外，定義自己的list並實現比較函數，該函數列表：

class MyList(list): 
    def __lt__(self, other): 
     return self[2] < other[2] 

q = [MyList(x) for x in n]

注意：您應該實現其他比較功能（請參閱functools.total_ordering關於如何輕鬆完成）。

來源

2017-08-26 07:01:38 AChampion

python heapq：如何使用列表列表中的第n個元素對堆進行排序？

回答

相關問題