title: How does heapq resolve equal values?
body: <p>Coming from Java, I am trying to implement <a href="https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode" rel="nofollow noreferrer">A* algorithm</a> in python and I'm having trouble sorting vertices in my graph that have equal f scores. I'm trying to do so using <code>heapq</code>, 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.</p>
  <p>An illustration of the behaviour is like so:</p>
  <pre><code>&gt;&gt;&gt; mylist = [1, 2, 5, 4, 3]
  &gt;&gt;&gt; heapq.heapify(mylist)
  &gt;&gt;&gt; mylist
  &gt;&gt;&gt; [1, 2, 3, 4, 5]
  &gt;&gt;&gt; heapq.heappush(mylist, 1)
  &gt;&gt;&gt; mylist
  &gt;&gt;&gt; [1, 2, 1, 4, 5, 3]
  </code></pre>
  <p>Here is the actual code I'm implementing for context:</p>
  <pre><code>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 &lt; other.total_cost
  
  def __eq__(self, other):
      if isinstance(other, Vertex):
          return self.total_cost == other.total_cost
      return NotImplemented
  </code></pre>