Python heapq：如何使用列表中第n个元素对堆进行排序？

Question

所以我有一些列表被添加到堆中；例如：

 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]]

- Aditya Pokharel

---

sorted(your_list_of_lists,key=lambda x:x[2]) - DYZ

你是只需要“排序”还是有多个插入和删除操作？ - AChampion

我不能使用其他东西。由于算法的时间复杂度非常紧，因此我需要节省一些大O。有没有办法让heapq本身以不同的顺序存储列表？（附注：我还编辑了帖子以澄清一些事情） - Aditya Pokharel

如果您只需要进行一次排序，那么sorted()是最快的选择。但如果您需要在多次push和pop操作中维护一个有序结构，则使用heapq更为合适。 - AChampion

AChampion - 我需要一个具有log(n)推入和弹出的排序队列。 - Aditya Pokharel

Answer 1

heapq不支持 key 函数以进行排序，因此您需要操作数据结构。将列表映射到 tuple(sort_value, list) 将允许您进行 log(n) 的推入和弹出：

 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])

或者，您可以定义自己的列表，并为该列表实现比较函数：

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

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

注意：您应该实现其他比较函数（请参阅functools.total_ordering以了解如何轻松地完成此操作）。

- AChampion