Comparing two different ways of finding the kth smallest element in a column wise and row wise sorted matrix[M][N]

Question

The first way:- As all rows are sorted, we can use the concept of merging M arrays into one using a min-heap. The procedure is:- Include the first element of each row into the heap, remove the minimum element and include the next element from the row from which the minimum is removed(the first min will be matrix[0][0] obv). Do it k times and complexity will be O(klogM)

The second way:- In the first way I did not use the fact that columns are also sorted. The idea here is that when a minimum element is removed from the heap, insert the right and the bottom element into the heap (unless it is already in the heap) Lets say our matrix is:-
5 7 8 9
6 9 10 13
7 11 12 15
8 13 16 17
I know the minimum element is matrix[0][0], so for k=1 ans will be 5 For values of k greater than 1, which is what we will want as k=1 is trivial At the first step I can include 7(0,1) and 6(1,0) (and make matrix[0][1]=-1 and matrix[1][0]=-1 to make it sure that we later know which element is in the heap) into the heap and then 6(1,0) will come out to be the second minimum.
Next step 9(1,1) and 7(2,0) will be added.
Now 7(0,1) will be removed and 8(0,2) will be added ( 9(1,1) is already in the heap , I made this entry in the matrix -1 for making it clear that it is already in the heap). And in this way at each step 1 element is removed and atmost 2 are added, so after doing k such removals from the heap we will get our k smallest elements.
Here the complexity comes out to be O(klogk) because at most logk is the height of the heap and we are doing operations on heap for k times, please correct me if I am wrong.

The second idea appears better at the first look. But for cases in which k greater than M
klogk is greater than klogM.
So is it the case that for k less than M second method is better, and for k greater than M first method?? Now because k is getting incremented at every step and the height is also getting incremented with k crossing another power of two. So my question is whether the complexity of the second approach really O(klogk)? Or by some careful analysis it is something lesser?

Answer 1

O(k log k) is really the best bound -- it's possible to get k elements in the priority queue even when k >> M. One simple tweak, however, drops the complexity to O(k log min(k, M, N)). Don't insert an element unless the elements above and to the left either don't exist or already have been removed from the queue. Then the positions of the elements in the queue are incomparable, which means that there are at most min(k, M, N) of them.