使用自定义数据类型Python的最小堆

Question

我想在Python中实现修复的快速行进方法。在文献中，这是使用最小堆实现的。由于它涉及多次添加、删除和重新排序数据结构，每次都提取最小的元素。因此，这些操作的复杂性最好是最小的。

我知道Python中有一个内置的heapq模块。它接受单个float值。然而，我需要存储对应于一个像素的3个不同的信息内容。有没有一种方法可以调整heapq以接受列表？

或者，是否存在具有此功能的不同数据结构？

Answer 1

heapq接受任何类型，只要它们是可订购的。项必须支持低于<的运算符或低于或等于<=的运算符（如果第一个运算符不可用，heapq将使用后者）。

例如，您可以使用元组（(priority, your_data_structure)）；元组根据其内容有一个相对顺序，从第一项开始。

或者，您可以使用实现__lt__、__le__、__gt__或__ge__中至少一个的自定义对象来实现它们之间的比较，从而定义排序（最好还包括__eq__相等方法）。然后functools. total_ordering()装饰器将为您的类提供剩余的方法：

from functools import total_ordering
@total_ordering
class PixelInfo(object):
    def __init__(self, r, g, b):
        self.r, self.g, self.b = r, g, b
    def __eq__(self, other):
        if not isinstance(other, type(self)): return NotImplemented
        return all(getattr(self, c) == getattr(other, c) for c in 'rgb')
    def __lt__(self, other):
        if not isinstance(other, type(self)): return NotImplemented
        return self.r + self.g + self.b < other.r + other.g + other.b

将是一个可订购的自定义类，heapq很乐意为您处理。