为元组数组定义堆键

Question

使用python堆实现的一个简单示例是

>>> 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文档明确地让音符如用法:

堆元素可以是元组.这对于在跟踪的主记录旁边分配比较值(例如任务优先级)非常有用:

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

因为实现heap使用默认排序元组

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

和Python按元素排序元组,确保首先要对元组进行排序的对象.