Python 如何让 heapq 评估特定属性的堆？

How to make heapq evaluate the heap off of a specific attribute?

提问by coffee

I wish to hold a heap of objects, not just numbers. They will have an integer attribute in them that the heap can sort by. The easiest way to use heaps in python is heapq, but how do I tell it to sort by a specific attribute when using heapq?

我希望持有一堆对象，而不仅仅是数字。它们将具有堆可以排序的整数属性。在 python 中使用堆的最简单方法是 heapq，但是在使用 heapq 时如何告诉它按特定属性排序？

采纳答案by eumiro

heapqsorts objects the same way list.sortdoes, so just define a method __cmp__()within your class definition, which will compare itself to another instance of the same class:

heapq以相同的方式list.sort对对象进行排序，因此只需__cmp__()在您的类定义中定义一个方法，它将自身与同一类的另一个实例进行比较：

def __cmp__(self, other):
    return cmp(self.intAttribute, other.intAttribute)

Works in Python 2.x.

在 Python 2.x 中工作。

In 3.x use:

在 3.x 中使用：

def __lt__(self, other):
    return self.intAttribute < other.intAttribute

回答by Daniel Stutzbach

Unfortunately, you can't, although this is an often requested feature.

不幸的是，您不能，尽管这是一个经常要求的功能。

One option would be to insert (key, value) tuples into the heap. However, that won't work if the values throw an exception when compared (they will be compared in the case of a tie between keys).

一种选择是将 (key, value) 元组插入堆中。但是，如果值在比较时抛出异常（它们将在键之间存在联系的情况下进行比较），则这将不起作用。

A second option would be to define a __lt__(less-than) method in the class that will use the appropriate attribute to compare the elements for sorting. However, that might not be possible if the objects were created by another package or if you need them to compare differently elsewhere in the program.

第二种选择是在类中定义一个__lt__（小于）方法，该方法将使用适当的属性来比较元素以进行排序。但是，如果对象是由另一个包创建的，或者如果您需要它们在程序中的其他地方进行不同的比较，则这可能是不可能的。

A third option would be to use the sortedlistclass from the blistmodule (disclaimer: I'm the author). The constructor for sortedlisttakes a keyparameter that lets you specify a function to return the sort key of an element, similar to the keyparameter of list.sortand sorted.

第三种选择是使用blist模块中的sortedlist类（免责声明：我是作者）。for 的构造函数接受一个参数，该参数允许您指定一个函数来返回元素的排序键，类似于and的参数。sortedlistkeykeylist.sortsorted

回答by Jander

According to the example from the documentation, you can use tuples, and it will sort by the first element of the tuple:

根据文档中的示例，您可以使用元组，它将按元组的第一个元素进行排序：

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

So if you don't want to (or can't?) do a __cmp__method, you can manually extract your sorting key at push time.

因此，如果您不想（或不能？）执行某个__cmp__方法，则可以在推送时手动提取排序键。

Note that if the first elements in a pair of tuples are equal, further elements will be compared. If this is not what you want, you need to ensure that each first element is unique.

请注意，如果一对元组中的第一个元素相等，则将比较其他元素。如果这不是您想要的，您需要确保每个第一个元素都是唯一的。

回答by Catbuilts

According to the Official Document, a solution to this is to store entries as tuples (please take a look at Sections 8.4.1and 8.4.2).

根据官方文档，解决方案是将条目存储为元组（请查看第8.4.1和8.4.2节）。

For example, your object is something like this in tuple's format (key, value_1, value_2)

例如，您的对象在tuple的格式中是这样的 (key, value_1, value_2)

When you put the objects (i.e. tuples) into heap, it will compare the first attribute in the object (in this case is key) to compare. If a tie happens, heap wills use the next attribute (i.e. value_1) and so on.

当您将对象（即元组）放入堆中时，它将比较对象中的第一个属性（在这种情况下是key）进行比较。如果出现平局，堆将使用下一个属性（即value_1），依此类推。

For example:

例如：

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)

Output:

输出：

                                      (0, 'one', 1)                                       
                (1, 'one', 1)                                (1, 'one', 4)                
    (1, 'one', 3)         (1, 'two', 3)         (1, 'two', 2)         (1, 'two', 5)     
(1, 'two', 11)

---

---

About pretty print a heap in python (updated the link): show_tree()

关于在 python 中漂亮地打印堆（更新了链接）：show_tree()

回答by DanGoodrick

You could implement a heapdict. Note the use of popitem() to get the lowest priority item.

你可以实现一个 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()

回答by Guru

I had the same question but none of the above answers hit the spot although some were close but not elaborated enough. Anyway, I did some research and tried this piece of code and hopefully this should be sufficient for someone next who is looking to get an answer:

我有同样的问题，但上述答案都没有找到，尽管有些答案很接近但不够详细。无论如何，我做了一些研究并尝试了这段代码，希望这对于下一个想要得到答案的人来说应该足够了：

The problem with using a tuple is it only uses the first item which is not very flexible. I wanted something similar to std::priority_queue in c++ like this: std::priority_queue<pair<int, int>, vector<pair<int, int>>, comparator> pq;where I could design my own comparator which is more common in real world applications.

使用元组的问题是它只使用第一项，这不是很灵活。我想要类似于 c++ 中的 std::priority_queue 的东西，就像这样： std::priority_queue<pair<int, int>, vector<pair<int, int>>, comparator> pq;我可以设计自己的比较器，这在现实世界的应用程序中更常见。

Hopefully the below snippet helps: https://repl.it/@gururajks/EvenAccurateCylinders

希望以下代码段有所帮助：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))

回答by Tushar Agarwal

I feel the simplest way is to override the existing cmp_lt function of the heapq module. A short example:

我觉得最简单的方法是覆盖 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