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

Question

我希望拥有一堆物品,而不仅仅是数字.它们将具有一个整数属性,堆可以按其排序.在python中使用堆的最简单方法是heapq,但是在使用heapq时如何告诉它按特定属性排序？

Answer 1

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

Answer 2

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

>>> 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__方法,您可以在推送时手动提取排序键.

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

Answer 3

Python 3 更新

这里的其他答案已经过时了：

• 有些是 Python 2 特定的。该__cmp__方法不再存在。
• 有些不反映最佳实践，并且仅__lt__针对PEP 8建议的所有丰富比较。
• 有些不使用现代工具，例如dataclasses、attrgetter或total_ordering。

具有数据类的现代解决方案

使用dataclasses，可以轻松制作具有自定义排序的数据持有者。例如，下面是一个从比较顺序中排除姓名字段的Person类：

from dataclasses import dataclass, field

@dataclass(order=True)
class Person:
    name: str = field(compare=False)
    age: int

actors = [
    Person('T Hanks', 65),
    Person('E Olson', 33),
    Person('A Tapping', 58),
]

这与堆完美配合：

>>> heapify(actors)
>>> heappop(actors)
Person(name='E Olson', age=33)
>>> heappop(actors)
Person(name='A Tapping', age=58)
>>> heappop(actors)
Person(name='T Hanks', age=65)

处理现有类

有时您必须使用所提供的数据，并且需要在不更改原始类的情况下控制比较顺序。

解决方案是添加一个包含新比较的包装器。这使得非原始数据及其类别保持不变。这是添加此类包装纸的现代配方：

from functools import total_ordering
from operator import attrgetter

def new_compare(*field_names):
    extract = attrgetter(*field_names)
    @total_ordering
    class ComparisonWrapper:
        def __init__(self, obj):
            self.obj = obj
        def __eq__(self, other):
            return extract(self.obj) == extract(other.obj)
        def __lt__(self, other):
            return extract(self.obj) < extract(other.obj)
    return ComparisonWrapper

例如，您可能会获得以下数据，但无法直接更改它或其类：

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    def __repr__(self):
        return f'Person({self.name!r}, {self.age})'

actors = [
    Person('T Hanks', 65),
    Person('E Olson', 33),
    Person('A Tapping', 58),
]

可以使用map()优雅地应用包装器。要解开数据，请访问obj属性：

>>> from heapq import heapify, heappop

>>> data = list(map(new_compare('age'), actors))
>>> heapify(data)
>>> heappop(data).obj
Person('E Olson', 33)
>>> heappop(data).obj
Person('A Tapping', 58)
>>> heappop(data).obj
Person('T Hanks', 65)

包装器与装饰元组

正如现代文档中所指出的，带有装饰元组的传统解决方案不再适用于某些基本用例。特别是，如果堆中的对象是函数，则 形式的元组(priority, task)在 Python 3 中不再有效，因为函数无法进行比较。

新的建议是使用包装器，例如：

from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

即使项目对象不具有可比性，这也始终有效。

Answer 4

根据官方文件，解决此问题的方法是将条目存储为元组（请参阅8.4.1和8.4.2节）。

例如，您的对象是类似tuple的格式 （键，值_1，值_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（）

Answer 5

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

Answer 6

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

使用元组的问题是它只使用第一项，这不是很灵活。我想要类似于 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))