Coming from Java, I am trying to implement A* algorithm in python and I'm having trouble sorting vertices in my graph that have equal f scores. I'm trying to do so using heapq, and after some debugging I noticed if I would like to push a vertex that has some f score equal to some other pre-existing vertices in the heap, the order would be messed up. I'm thinking of implementing my own priority queue now. I would like to know how this works.
An illustration of the behaviour is like so:
>>> 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]
Here is the actual code I'm implementing for context:
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
"Heap" doesn't mean "sorted" (if it did, you couldn't build it for arbitrary values in O(n) time). It means it satisfies the heap invariant, for a min-heap like Python's, this just means that the smallest value is at the top (if there's a tie, an arbitrary value wins), and that each node's children are always equal to or larger than the node. You find the children for a node at index i by looking at index 2*i+1 and 2*i+2, so in your example, putting P under each parent, and C under each of their children, we have:
[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)
As you can see, in each case, the P value is less than or equal to all of its children; the heap-invariant is maintained, which is all that is necessary for heappop, heappush, etc. to continue to work.
Note that for objects like your Vertex class, where the comparison is based on one value, but the objects have other state, a heap isn't stable; two objects with the same total_cost could come out in either order, regardless of which was placed in the heap first. To avoid this problem, you have to add your own fallback comparison by "decorating" each value. A simple approach would be:
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]