Как заставить heapq вычислять кучу определенного атрибута? - PullRequest
Новая
       5

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

32 голосов
/ 17 октября 2010

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

Ответы [ 5 ]

49 голосов
/ 17 октября 2010

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
38 голосов
/ 17 октября 2010

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

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

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

5 голосов
/ 06 июля 2018

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

Например, ваш объект выглядит примерно так в формате tuple . (ключ, значение_1, значение_2)

Когда вы помещаете объекты (т.е. кортежи ) в heap , он сравнивает первый атрибут объекта (в данном случае это key ) с сравнить. Если происходит связывание, в куче будет использоваться следующий атрибут (т. Е. value_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 ()

3 голосов
/ 17 октября 2010

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

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

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

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

0 голосов
/ 15 февраля 2019

Вы могли бы реализовать heapdict.Обратите внимание на использование popitem () для получения элемента с самым низким приоритетом.

import heapdict as hd
import string
import numpy as np

h = hd.heapdict()
keys = [char for char in string.ascii_lowercase[:10]]
vals = [i for i in np.random.randint(0,10, 10)]
for k,v in zip(keys,vals):
    h[k] = v
for i in range(len(vals)):
    print h.popitem()
...