Which Node Is Popped First in Priority Queue if Two Are Equal Weight

Question

I am working with this GraphSearch psuedo-code algorithm to find the shortest path to a goal from a starting position:

function GRAPH-SEARCH(problem,fringe,strategy) return a solution, or failure
   closed <-- an empty set
   fringe <-- INSERT(MAKE-NODE(INITIAL-STATE[problem]),fringe)
   loop do
      if fringe is empty then return failure
      node <-- REMOVE-FRONT(fringe,strategy)
      if STATE[node] is not in closed then
         add STATE[node] to closed
         for child-node in EXPAND(STATE[node],problem) do
            fringe <-- INSERT(child-node,fringe)
         end
   end

I am implementing the A* stretegy of searching for a goal from a starting position. A* search makes use of the formula:

f(n) = g(n) + h(n)

where g(n) is the cost to get to the current child-node, h(n) is the heuristic value to get to the goal (we are assuming the heuristic determined is admissable), and f(n) is the combined value we assign to that node in the fringe.

In A* search, a PriorityQueue is used to determine which child-node to pop() next to test for the goal state and/or expand to more children, which in this case is the child-node with the lowest value.

Here is my question:

I have a current PriorityQueue as follows:

     S -> B = 1 + 3 = 4  // The cost to B + the heuristic value to goal
     S -> A = 1 + 3 = 4  // The cost to A + the heuristic value to goal
          S = 0 + 0 = 0  // Has been popped & expanded

Where S is the starting position, and A and B are child nodes. There are two paths that are assigned the next lowest value 4, so which path does a PriorityQueue pop() next?

Answer 1

I have learned that by nature of a PriorityQueue, if the priority values of the next items are equal, then the structure is simply treated as a Queue.

In this case that means that since S -> A = 1 + 3 = 4 was the first in, it will be the first out.