Как сделать 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

К сожалению, вы не можете, хотя это часто запрашиваемая функция.

Одним из вариантов было бы вставить (ключ, значение) кортежи в кучу. Однако это не будет работать, если значения генерируют исключение при сравнении (они будут сравниваться в случае связи между клавишами).

Второй вариант заключается в определении метода __lt__ (меньше) в классе, который будет использовать соответствующий атрибут для сравнения элементов для сортировки. Однако это может быть невозможно, если объекты были созданы другим пакетом или если вам нужно их сравнивать по-другому в другом месте программы.

Третий вариант заключается в использовании класса sortedlist из модуля blist (отказ от ответственности: я автор). Конструктор sortedlist принимает параметр key, который позволяет задать функцию, чтобы вернуть ключ сортировки элемента, аналогично параметру list.sort и sortedkey.

Answer 3

Согласно примеру, из documentation, вы можете использовать кортежи, и он будет сортировать первый элемент кортежа:

>>> 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__, вы можете вручную извлечь свой ключ сортировки в момент времени.

Обратите внимание, что если первые элементы в паре кортежей равны, будут сравниваться другие элементы. Если это не то, что вы хотите, вам нужно убедиться, что каждый первый элемент уникален.