мини-куча с пользовательскими типами данных Python?

Question

Я хочу реализовать метод быстрого марширования для Inpainting в Python. В литературе это было реализовано с использованием мини-кучи. Так как это связано с добавлением, удалением и переупорядочением структуры данных много раз и каждый раз при извлечении наименьшего элемента. Поэтому сложность этих операций должна быть минимальной.

Я знаю, что есть встроенный модуль heapq в Python. Он принимает одно значение 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 был бы счастлив обрабатывать для вас.