# 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))

• Sorry. My question was not specific to heap. I know that each insertion in heap is log(n), but I specifically wanted to know how big the heap would grow. Since I will not be adding the nodes that have been visited into the heap, I am trying to understand how many elements at max the heap will hold for a 2d matrix if I am traversing the matrix in BFS manner – pynoob Apr 23 '17 at 17:14
• Thanks @D.W for guiding me towards improving the question. I have added my understanding for the upper bound in the question. – pynoob Apr 23 '17 at 17:30

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.
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.