0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – pynoob Apr 23 '17 at 17:14
  • $\begingroup$ Thanks @D.W for guiding me towards improving the question. I have added my understanding for the upper bound in the question. $\endgroup$ – pynoob Apr 23 '17 at 17:30
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.