python - 具有自定义数据类型Python的最小堆？

Question

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

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

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

Answer 1

heapq采取任何类型，只要它们是可订购的。这些项目必须支持 <低于或 <=小于或等于运算符(如果第一个运算符不可用， heapq 将使用后者)。

例如，您可以使用元组 ( (priority, your_data_structure) )；元组具有基于其内容的相对顺序，从第一项开始。

或者您可以使用至少实现 __lt__ 之一的自定义对象, __le__ , __gt__或__ge__实现它们之间的比较，从而定义排序(最好也包括 __eq__ 相等方法)。 functools. total_ordering() decorator然后将为您的类提供剩余的方法:

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我们很乐意为您服务。