What’s the best approach for finding the kth smallest elements on a min-heap with n elements in O(k log k) time. Assume that the original min-heap is

What’s the best approach for finding the kth smallest elements on a min-heap with n elements in O(k log k) time.
Assume that the original min-heap is called HO and the auxiliary min-heap is named HA.
Initially, the element at the top of HO, the minimum one, is inserted into the HA. However, here we do not do the operation of extract-min with HO. HeapEle is the data structure for the elements in the heap.

Heap HO;
Heap HA;
HeapEle FindKthEle( int k )
{
    HeapEle he;//it is a heap element;
    int rank=1;
    HA.Insert(HO.min);
    while( true )
    {
        he=HA.ExtractMin()//return the minimum element and delete it from the HA heap
        if( rank==k )
        {
          return he;
        }
        else
        {
          rank++;//each time insert two elements and get one ‘rank’th element, so the number of elements in the min heap is from 1,2…15 
          HA.Insert(he.Left);//insert the left and right children in HO into the HA
          HA.Insert(he.Right);
        }
    }
}

Every while-loop the "rank"th smallest element can be gotten. So we need k loops to get the kth smallest elements. Because the size of the auxiliary heap is always less than k, actaully every while-loop the size of the auxiliary heap increases by one, and the original heap HO has no operation during the finding, the running time is O(klgk)

Given a n*m matrix having numbers such that each row and each column sorted. Now print the numbers in present in the matrix in sorted order.. ps: He g

Given a n*m matrix having numbers such that each row and each column sorted. Now print the numbers in present in the matrix in sorted order..
ps: He gave me the hint as, we can rearrange the matrix.
1 3 7
2 4 8
9 10 13

put all first elements of the each row at min heap, heapify the min heap, get the root, insert the root’s row’s next node, heapify the min heap, get the root, repeat this operation until all elements in the matrix are sorted
O(nmlogn) where n is row, m is column

Give efficient algorithms for finding the largest k values (in order) out of

Give efficient algorithms for finding the largest k values (in order) out of
a set of n, using comparisons only (e.g. no hashing), in the case where:
(a) k = 3 (b) k = n/2; (c) k = log(n).
(You can use a different algorithm for each case.)
State the asymptotic worst-case running time of your algorithms.
For (a), we use tournament algorithm, which has done this by n-1+logn-1+logn-2+logn-1, O(n+klogn-m) comparison
For (b), we use selection algorithm, which has done this by O(n) if the pivot is the median of the median of the array
For (c), we use minheap, which has done this by O(nlogk), notice when we heapify the min heap, do comparison on two child nodes first, and then swap the parent node with the smaller one, that is where the logk come from

Find the kth min/max out of n numbers,

Find the kth min/max out of n numbers,

1) max heap, heap size k, O(nlogk)
2) 2^32 bit vector, use the value of integer as index to set bit vector, then the indexes of max k set bits are max k integers, O(n)
3) selection algorithm to find kth number then scan the array again to find the value smaller than this number O(n)