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

Ответ 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

Ответ 2

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

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

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

Ответ 3

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

Например, ваш объект выглядит примерно так в формате кортежа (ключ, значение_1, значение_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()

Ответ 4

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

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

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

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

Ответ 5

Вы могли бы реализовать 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()

Ответ 6

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

Проблема с использованием кортежа состоит в том, что он использует только первый элемент, который не очень гибок. Я хотел что-то похожее на std :: priority_queue в c++, например так: std::priority_queue<pair<int, int>, vector<pair<int, int>>, comparator> pq; где я мог бы разработать свой собственный компаратор, который более распространен в реальных приложениях.

Надеемся, что приведенный ниже фрагмент поможет: https://repl.it/@gururajks/EvenAccurateCylinders

import heapq
class PQNode:

    def __init__(self, key, value):
        self.key = key
        self.value = value

    # compares the second value
    def __lt__(self, other):
        return self.value < other.value

    def __str__(self):
        return str("{} : {}".format(self.key, self.value))

input = [PQNode(1, 4), PQNode(7, 4), PQNode(6, 9), PQNode(2, 5)]
hinput = []
for item in input:
    heapq.heappush(hinput, item)

while (hinput):
    print (heapq.heappop(hinput))