为元组数组定义堆键

Question

from heapq import heappush, heappop
heap = []
data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
for item in data:
    heappush(heap, item)

在更复杂的情况下，我有一个元组数组，例如

tuples = [(5,"foo",True),(2,"bar", False),(8,"foobar",True)]

并且想使用每个元组的第一个条目作为堆键，即元组应该根据元组中的数字排序。

我该怎么做？

Answer 1

您可以简单地按原样使用元组。例如用法的Python documentation explicitly makes note：

Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked:
>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

只需将元组推入堆，并在需要时将其弹出：

>>> from heapq import heappush, heappop
>>> 
>>> heap = []
>>> tuples = [(5,"foo",True),(2,"bar", False),(8,"foobar",True)] 
>>> 
>>> for tup in tuples:
...     heappush(heap, tup)
... 
>>> heappop(heap)
(2, 'bar', False)

因为the implementation for heap对元组使用默认排序

while pos > startpos:
    ...
    if newitem < parent:
        ...
    ...
...

和 Python 按元素对元组进行排序，确保要对元组进行排序的对象排在第一位。

为元组数组定义堆键

Define heap key for an array of tuples

python

heap