我希望拥有一堆对象,而不仅仅是数字。它们将具有堆可以排序的整数属性。在 python 中使用堆的最简单方法是 heapq,但是在使用 heapq 时如何告诉它按特定属性排序?
8 回答
根据文档中的示例,您可以使用元组,它将按元组的第一个元素排序:
>>> 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')
因此,如果您不想(或不能?)执行某个__cmp__
方法,您可以在推送时手动提取排序键。
请注意,如果一对元组中的第一个元素相等,则将比较其他元素。如果这不是您想要的,您需要确保每个第一个元素都是唯一的。
heapq
以相同的方式list.sort
对对象进行排序,因此只需__cmp__()
在类定义中定义一个方法,该方法会将自身与同一类的另一个实例进行比较:
def __cmp__(self, other):
return cmp(self.intAttribute, other.intAttribute)
在 Python 2.x 中工作。
在 3.x 中使用:
def __lt__(self, other):
return self.intAttribute < other.intAttribute
根据官方文档,解决方案是将条目存储为元组(请查看第8.4.1和8.4.2节)。
例如,您的对象是这样的tuple格式 (key, value_1, value_2)
当您将对象(即tuples)放入heap时,它将使用对象中的第一个属性(在本例中为key)进行比较。如果出现平局,堆将使用下一个属性(即value_1)等等。
例如:
import heapq
heap = []
heapq.heappush(heap, (0,'one', 1))
heapq.heappush(heap, (1,'two', 11))
heapq.heappush(heap, (1, 'two', 2))
heapq.heappush(heap, (1, 'one', 3))
heapq.heappush(heap, (1,'two', 3))
heapq.heappush(heap, (1,'one', 4))
heapq.heappush(heap, (1,'two', 5))
heapq.heappush(heap, (1,'one', 1))
show_tree(heap)
输出:
(0, 'one', 1)
(1, 'one', 1) (1, 'one', 4)
(1, 'one', 3) (1, 'two', 3) (1, 'two', 2) (1, 'two', 5)
(1, 'two', 11)
关于在 python 中漂亮地打印一个堆(更新了链接):show_tree()
我觉得最简单的方法是覆盖 heapq 模块现有的 cmp_lt 函数。一个简短的例子:
import heapq
# your custom function. Here, comparing tuples a and b based on their 2nd element
def new_cmp_lt(self,a,b):
return a[1]<b[1]
#override the existing "cmp_lt" module function with your function
heapq.cmp_lt=new_cmp_lt
#Now use everything like normally used
我有同样的问题,但上述答案都没有到位,尽管有些答案很接近但不够详细。无论如何,我做了一些研究并尝试了这段代码,希望这对于下一个希望得到答案的人来说已经足够了:
使用元组的问题是它只使用第一项,这不是很灵活。我想要类似于 c++ 中的 std::priority_queue 的东西,如下所示:
std::priority_queue<pair<int, int>, vector<pair<int, int>>, comparator> pq;
我可以设计自己的比较器,这在现实世界的应用程序中更常见。
希望下面的代码片段有所帮助: https ://repl.it/@gururajks/EvenAccurateCylinders
import heapq
class PQNode:
def __init__(self, key, value):
self.key = key
self.value = value
# compares the second value
def __lt__(self, other):
return self.value < other.value
def __str__(self):
return str("{} : {}".format(self.key, self.value))
input = [PQNode(1, 4), PQNode(7, 4), PQNode(6, 9), PQNode(2, 5)]
hinput = []
for item in input:
heapq.heappush(hinput, item)
while (hinput):
print (heapq.heappop(hinput))
不幸的是,你不能,尽管这是一个经常被要求的功能。
一种选择是将 (key, value) 元组插入堆中。但是,如果值在比较时抛出异常(它们将在键之间存在关联的情况下进行比较),则这将不起作用。
第二种选择是在__lt__
类中定义一个(小于)方法,该方法将使用适当的属性来比较元素以进行排序。但是,如果对象是由另一个包创建的,或者如果您需要它们在程序的其他地方进行不同的比较,这可能是不可能的。
第三种选择是使用blist模块中的sortedlist类(免责声明:我是作者)。for 的构造函数接受一个参数,该参数允许您指定一个函数以返回元素的排序键,类似于and的参数。sortedlist
key
key
list.sort
sorted
你可以实现一个 heapdict。请注意使用 popitem() 来获取最低优先级的项目。
import heapdict as hd
import string
import numpy as np
h = hd.heapdict()
keys = [char for char in string.ascii_lowercase[:10]]
vals = [i for i in np.random.randint(0,10, 10)]
for k,v in zip(keys,vals):
h[k] = v
for i in range(len(vals)):
print h.popitem()
有一个模块叫heaps
. Github 地址是https://github.com/gekco/heapy。您可以在类的实例化或从数组创建堆时应用自己的键/排序函数,这非常有用,因为这样可以节省您在每次执行操作时将其添加为参数。
我想要列表的示例,其中元组最后一个位置的最小元素位于堆顶部:
>>> from heapy.heap import Heap
>>> a = [(3, 5, 10), (-5, 3, 8), (7, 8, 9), (-4, 0, 2)]
>>> x = Heap.from_array(a, key=lambda t : t[-1])
>>> x.length
4
>>> x.top()
(-4, 0, 2)
>>> x.insert((-1, 0, 1))
>>> x.length
5
>>> x.top()
(-1, 0, 1)
>>> a
[(3, 5, 10), (-5, 3, 8), (7, 8, 9), (-4, 0, 2)]