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个元素对堆进行排序？

回答

相关问题