heapq 是如何解析相等值的？

Question

来自 Java，我正在尝试在 python 中实现 A* algorithm，但我在对图表中具有相同 f 分数的顶点进行排序时遇到问题。我正在尝试使用 heapq 来这样做，经过一些调试后我注意到如果我想推送一个 f 分数等于堆中其他一些预先存在的顶点的顶点，顺序会被弄乱向上。我现在正在考虑实施自己的优先级队列。我想知道这是如何工作的。

该行为的示例如下：

>>> mylist = [1, 2, 5, 4, 3]
>>> heapq.heapify(mylist)
>>> mylist
>>> [1, 2, 3, 4, 5]
>>> heapq.heappush(mylist, 1)
>>> mylist
>>> [1, 2, 1, 4, 5, 3]

这是我为上下文实现的实际代码：

class Node(object):

def __init__(self, name, x_coordinate, y_coordinate, obstacle_flag=False):
    self.name = name  # possible values should only be ' ', 'A-Z', '*'
    self.coordinates = (x_coordinate, y_coordinate)  # this will uniquely identify the node
    self.obstacle = obstacle_flag  # if the name is '*' the obstacle is set to True
    self.neighbors = {}  # list of neighbors of this node
    self.set_obstacle()

...

class Vertex(Node):
def __init__(self, name, x_coordinate, y_coordinate, obstacle_flag):
    super(Vertex, self).__init__(name, x_coordinate, y_coordinate, obstacle_flag)
    self.g_actual_cost = 10000  
    self.h_cost = 0  # the cost given by the heuristic function
    self.previous_vertex = None
    self.total_cost = self.g_actual_cost + self.h_cost

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

def __eq__(self, other):
    if isinstance(other, Vertex):
        return self.total_cost == other.total_cost
    return NotImplemented

Answer 1

顺序没有乱。堆应该具有所有索引：

a[i] <= a[2*i + 1]
a[i] <= a[2*i + 2]

这并不意味着数组已排序。在您的情况下，堆不变量仍然得到满足，您可以将其作为优先级队列使用。

>>> heap = [1, 2, 1, 4, 5, 3]
>>> import heapq
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
2
>>> heap
[3, 4, 5]

Answer 2

“堆”并不意味着“排序”（如果是，则无法在 O(n) 时间内为任意值构建它）。这意味着它满足堆不变性，对于像 Python 这样的 min-heap，这仅意味着最小值在顶部（如果有平局，则任意值获胜），并且每个节点的 children 总是等于或大于节点。您通过查看索引 2*i+1 和 2*i+2 找到索引 i 处节点的 children，因此在您的示例中，将 P 放在每个 parent，并且 C 在他们的每个 children 下，我们有：

[1, 2, 1, 4, 5, 3]
#P  C  C
#0  1  2

[1, 2, 1, 4, 5, 3]
#   P     C  C
#   1     3  4

[1, 2, 1, 4, 5, 3]
#      P        C
#      2        5  (only one child since heap lacks another element)

如您所见，在每种情况下，P 值都小于或等于其所有 children； heap-invariant 得到维护，这是 heappop、heappush 等继续工作所必需的。

请注意，对于 objects，例如您的 Vertex class，比较基于一个值，但 objects 具有其他状态，堆不是'稳定；具有相同 total_cost 的两个 objects 可以按任何顺序出现，而不管哪个先放在堆中。为避免此问题，您必须通过“装饰”每个值来添加自己的回退比较。一个简单的方法是：

 from itertools import count

 original_list = [Vertex(...), Vertex(...), ...]  # Define initial list of vertices
 numbermaker = count()
 decorated_list = [(v, next(numbermaker)) for v in original_list]
 heapq.heapify(decorated_list)

 # When you want to add new elements:
 heapq.heappush(decorated_list, (Vertex(...), next(numbermaker)))

 # When you want to get the top of the heap's value:
 top = decorated_list[0][0]  # First [0] gets decorated top, second strips decoration

 # When you want to pop off the top:
 top = heapq.heappop(decorated_list)[0]

heapq 是如何解析相等值的？

How does heapq resolve equal values?

python

priority-queue

heapq