Как сделать heapq оценивать кучу определенного атрибута?

Я хочу держать кучу объектов, а не только цифр. Они будут иметь в них целочисленный атрибут, который куча может сортировать. Самый простой способ использовать кучи в python - heapq, но как я могу сказать, что он сортирует по определенному атрибуту при использовании heapq?

python,data-structures,heap,

25

Ответов: 4


35 ов принято

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

28 ов

В соответствии с примером из документации вы можете использовать кортежи и сортировать по первому элементу кортежа:

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

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


3

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

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

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

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


0

Согласно официальному документу , решение для этого - хранить записи в виде кортежей (см. Разделы 8.4.1 и 8.4.2 ).

Например, ваш объект выглядит примерно так в корневом формате (key, value_1, value_2)

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

Например:

import heapq

heap = []
heapq.heappush(heap, (0,'one', 1))
heapq.heappush(heap, (1,'two', 11))
heapq.heappush(heap, (1, 'two', 2))
heapq.heappush(heap, (1, 'one', 3))
heapq.heappush(heap, (1,'two', 3))
heapq.heappush(heap, (1,'one', 4))
heapq.heappush(heap, (1,'two', 5))
heapq.heappush(heap, (1,'one', 1))

show_tree(heap)

Вывод:

                                      (0, 'one', 1)                                       
                (1, 'one', 1)                                (1, 'one', 4)                
    (1, 'one', 3)         (1, 'two', 3)         (1, 'two', 2)         (1, 'two', 5)     
(1, 'two', 11)

О красивой печати кучи в python: show_tree ()

Python, структуры данных, куча,
Похожие вопросы