Почему элементы в моем heapq не упорядочены по python? - PullRequest
Новая
       38

Почему элементы в моем heapq не упорядочены по python?

0 голосов
/ 04 октября 2018

Я использую простой heapq в python с пользовательскими элементами, для которых я реализовал функцию lt . 

class Edge:
    def __init__(self, cost, u, v):
        self.u = u
        self.v = v
        self.cost = cost
    def weight(self):
        w = self.cost
        v = self.v
        while v.parent is not None:
            w += v.const
            v = v.parent
        return w

    def __lt__(self, other):
        return self.weight() < other.weight()

Затем я сохраняю кучу этих элементов в другом массиве под названием P: 

class Vertex:
    def __init__(self, node=None):
        #other stuff omited ##### 
        self.P = []

    def add_incoming_nodes(self, subgraph):
        for node, costs in subgraph.items():
            #if costs[self.vertex] is not 0: #node is not self
            #push endpoints of the edge from another vertex to this vertex
            heapq.heappush(self.P, Edge(costs[self.vertex], node, self))

Проблема в том, что, когда я heappop элемент, я ожидал бы, что это будет самый маленький элемент в моем массиве правильно?Но это утверждение здесь не так 

#select arbitrary vertex
a = all_nodes[0]
while a.P: #while P[a] is not ∅
    edge = heapq.heappop(a.P)
    for a_edge in a.P: 
        assert edge.weight() < a_edge.weight()
...