It's true that this will always be a common ancestor, but I think if you're trying to find the actual merge-base, then it's possible that this will return the wrong answer.  The pq will order the traversal by timestamp. It's possible that the commit with the earliest timestamp will not be the "correct" merge-base.

Check out the merge base code here: https://github.com/libgit2/libgit2/blob/development/src/merge.c#L162, which keeps a list of all the possible merge bases and filters out all the ones that become STALE at the end of the traversal. The `mark_parents` function here https://github.com/libgit2/libgit2/blob/development/src/graph.c#L32 is very similar to the merge-base algorithm. It might be easier to modify that to return the merge base.