heapq custom сравнить с - PullRequest
Новая
       16

heapq custom сравнить с

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

Я пытаюсь определить обычный метод, чтобы сделать упорядоченную вставку в приоритетную очередь в python, но не получаю ожидаемых результатов. После определения метода вставки в очередь, как показано ниже: 

def insert(self, node):
    if isinstance(node, treeNode):
        heapq.heappush(self._frontier, (node._f, node))
    else:
        print("Error. It is not a node.")

И реализация следующего lt в классе 'node': 

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

Вставка не выполняется значением атрибута 'f', которое я хочу сделать, вставлять в порядке возрастания, определяемом этим значением. Любая помощь будет высоко ценится.

Ex сбоя: 

[(141.09530289033592, <treeNode.treeNode object at 0x7f08bb840fd0>), (484.8315227978057, <treeNode.treeNode object at 0x7f08bb849da0>), (390.0514031446352, <treeNode.treeNode object at 0x7f08bb840e48>)]

Он только помещает в первую позицию самое низкое значение, что имеет смысл, поскольку используется приоритетная очередь, но затем следующие не сортируются пользовательским методом, который я хочу объявить.

1 Ответ

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

Как упомянул @Bakuriu, heapq поддерживает только инвариант heap , если вы хотите получить элементы по порядку, используйте nsmallest , например: 

import heapq


class TreeNode:
    def __init__(self, f):
        self.f = f

    def __repr__(self):
        return 'f: {}'.format(self.f)

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


class Frontier:
    def __init__(self):
        self.frontier = []

    def insert(self, node):
        if isinstance(node, TreeNode):
            heapq.heappush(self.frontier, (node.f, node))
        else:
            print("Error. It is not a node.")

    def __len__(self):
        return len(self.frontier)


t = Frontier()

for n in [TreeNode(141.09530289033592), TreeNode(484.8315227978057), TreeNode(390.0514031446352)]:
    t.insert(n)

print(heapq.nsmallest(len(t), t.frontier))

выход 

[(141.09530289033592, f: 141.09530289033592), (390.0514031446352, f: 390.0514031446352), (484.8315227978057, f: 484.8315227978057)]
...