如何在保留列表的同时通过某个索引从矩阵中 heappush 列表？

Question

假设我有一个列表：

l1 = [[1, 3], [3, 2], [2, 1]]

我想将 l1 中的每个项目推送到二进制堆，'memory' 但在二进制堆中按 each_item[-1] 排序。

我试过：heapq.heappush(_heap, item=itemgetter(-1)) 和使用匿名函数的等价物，但我得到：

TypeError: heappush() takes no keyword arguments

Answer 1

一个选项是围绕 heapq 函数制作小型包装器以 prepend/extract 排序值 to/from 项目以一致的方式：

def heappush(h, item, key=lambda x: x):
    heapq.heappush(h, (key(item), item))

def heappop(h):
    return heapq.heappop(h)[1]

def heapify(h, key=lambda x: x):
    for idx, item in enumerate(h):
        h[idx] = (key(item), item)
    heapq.heapify(h)

正在使用您的样本进行测试：

l1 = [[1, 3], [3, 2], [2, 1]]
h = []
for item in l1:
    heappush(h, item, key=itemgetter(-1))

while h:
    print(heappop(h))

打印：

[2, 1]
[3, 2]
[1, 3]

请注意，您可以使用 h=l1; heapify(h, key=itemgetter(-1))，这应该比单独 heappush 每个项目更快。

Answer 2

您可以将堆中的条目存储为 3 元素元组，包括最后一个元素、条目计数和实际项目。这样，项目将按照它们的最后一个值进行排序，条目计数确保排序稳定性（即，最后一个元素相同的两个项目按照它们添加的顺序返回）：

>>> import heapq
>>> heap = []
>>> l1 = [[1, 3], [3, 2], [2, 1]]
>>> for count, item in enumerate(l1):
...     heapq.heappush(heap, (item[-1], count, item))
... 
>>> while heap:
...     print(heapq.heappop(heap)[-1])
... 
[2, 1]
[3, 2]
[1, 3]

Answer 3

我喜欢 Eugene 的解决方案，但如果经常使用这个特殊的元组，可以定义一个自定义对象来实现这一点，如下所示：

from heapq import heappush, heappop

class MyTupleHeapObj(object):
    def __init__(self,val): self.val = val
    def __lt__(self,other): return self.val[-1] < other.val[-1]
    def __eq__(self,other): return self.val == other.val
    def __str__(self): return str(self.val)

h = []
for item in [[1, 3], [3, 2], [2, 1]]:
    heappush(h, MyTupleHeapObj(item))

while h:
    print heappop(h)

打印以下内容：

[2, 1]
[3, 2]
[1, 3]

如何在保留列表的同时通过某个索引从矩阵中 heappush 列表？

How do I heappush lists from a matrix by a certain index while preserving the list?

python

binary-heap

python-2.7

python-3.x