2

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

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

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

4

1 回答 1

3

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很乐意为您处理。

于 2013-06-21T13:12:33.363 回答