Time complexity of BFS with min heap Given a matrix of size m x n, I am trying to traverse it using BFS from top left corner to bottom right corner. Instead of using a normal queue for BFS, I am using a min heap. For each cell, I am inserting the adjacent values (top, left, right, bottom) in a min heap. 
I am specifically trying to understand how big the heap would grow. I know that BFS traversing would cost me O(mn) and each heap insertion would cost me O(logk) where k is the size of the heap. Here I am trying to figure out how big can be k. 
e.g

[
[1,2,3,4,5],
[2,3,4,1,3],
[4,3,2,1,4]
]


My thoughts are that at max there can be m x n elements in the heap. So the overall complexity can be O(mnlogmn). But when I run through some examples, I think not everything will be in the heap all the time. A single cell can at max insert 2 elements (other 2 would have been inserted by some other cell already). So based on the examples I am thinking that it should be O(mnlog(m+n))
Yes.  Both bounds are valid.  There's not much difference between the two bounds.

There are certainly at most $mn$ items in the queue at any time, as there are only $mn$ possible items.  Consequently, the running time is at most $O(mn \log(mn))$.

By analyzing how BFS visits nodes and the size of the "fringe", one can show that the size of the fringe is most $m+n$.  In particular, the fringe is a path that goes from somewhere on the top of the matrix to somewhere on the left of the matrix, by going only down, left, or diagonally down-and-left (but never right or up).  Thus the fringe can include at most $m+n$ cells.  This means that at every stage, the size of the heap is at most $m+n$, so $O(mn\log(m+n))$ is also a valid upper bound on the running time.

These two bounds are pretty close, so either is a reasonable upper bound on the running time.

Caveat: there are multiple heap data structures, with different running times for the heap operations.  This answer assumes you are using a heap data structure where inserting into a heap containing $k$ items can be done in $O(\log k)$ time.