Как инвертировать порядок элементов в куче heapq с помощью функций сравнения объектов? - PullRequest
Новая
       10

Как инвертировать порядок элементов в куче heapq с помощью функций сравнения объектов?

0 голосов
/ 23 ноября 2018

Прежде всего, я прочитал этот ТАК вопрос , но на самом деле он не включает в себя мой желаемый подход.Кроме того, отрицание фактических значений неприменимо для моего варианта использования.

Документы Heapq: https://docs.python.org/3.6/library/heapq.html

Предположим, у меня есть список объектов класса данных в моей куче.Только свойство a определяет порядок объектов. 

import heapq
from dataclasses import dataclass

@dataclass
class C:
    a: int
    b: int
    def __lt__(self, other):
        return self.a < other.a

l=[C(2,1),C(9,109),C(2,4),C(9,4)]

print(heapq.heappop(l)) # C(a=2, b=1)
print(heapq.heappop(l)) # C(a=2, b=4)
print(heapq.heappop(l)) # C(a=9, b=109)
print(heapq.heappop(l)) # C(a=9, b=4)

Теперь я хочу иметь инвертированный порядок.Поэтому я изменил строку return self.a < other.a на return self.a > other.a.Результат: 

import heapq
from dataclasses import dataclass

@dataclass
class C:
    a: int
    b: int
    def __lt__(self, other):
        return self.a > other.a

l=[C(2,1),C(9,109),C(2,4),C(9,4)]

print(heapq.heappop(l)) # C(a=2, b=1)
print(heapq.heappop(l)) # C(a=9, b=109)
print(heapq.heappop(l)) # C(a=9, b=4)
print(heapq.heappop(l)) # C(a=2, b=4)

Желаемым результатом должно быть одно из четырех решений: 

C(a=9, b=109)   C(a=9, b=4)      C(a=9, b=109)  C(a=9, b=4)    
 C(a=9, b=4)    C(a=9, b=109)    C(a=9, b=4)    C(a=9, b=109) 
 C(a=2, b=1)    C(a=2, b=1)      C(a=2, b=4)    C(a=2, b=4)  
 C(a=2, b=4)    C(a=2, b=4)      C(a=2, b=1)    C(a=2, b=1)

Вероятно, не все пары объектов сравниваются по heapq, что объясняет странноепорядок.Однако возможно ли получить инвертированный заказ?

Нужно ли предоставлять больше методов сравнения объектов?

object.__lt__(self, other)
object.__le__(self, other)
object.__eq__(self, other)
object.__ne__(self, other)
object.__gt__(self, other)
object.__ge__(self, other)

Если у вас совершенно другой подход, не стесняйтесь!

1 Ответ

0 голосов
/ 23 ноября 2018

Вам нужно превратить l в кучу, используя heapify

from heapq import heapify, heappop
from dataclasses import dataclass

@dataclass
class C:
    a: int
    b: int
    def __lt__(self, other):
        return self.a > other.a

l=[C(2,1),C(9,109),C(2,4),C(9,4)]

heapify(l)    

while l:
    print(heappop(l))

отпечатков 

C(a=9, b=4)
C(a=9, b=109)
C(a=2, b=1)
C(a=2, b=4)
...