3

Min heap with P distinct element is given. We want to find Kth (k <= Sqrt (P)) smallest element in this heap using the best algorithm in O(K log K). (There are k-1 numbers smaller than it exactly).

What is the algorithm in this time complexity? It means, how does it work?

HoRn
  • 1,458
  • 5
  • 20
  • 25
user3661613
  • 107
  • 1
  • 9
  • 5
    why restriction on K is given? HOw affect the algortihm? – user3661613 Nov 26 '20 at 19:08
  • https://stackoverflow.com/questions/47892037/finding-k-smallest-elements-in-a-min-heap-worst-case-complexity – fps Nov 26 '20 at 19:11
  • 1
    @fps restriction on K is given here – user3661613 Nov 26 '20 at 19:16
  • 2
    I stand corrected, then. I closed the question too quickly, voting to reopen. Maybe you could edit your question, so that it is crystal-clear that the sqrt restriction makes your question different to the one I've linked to – fps Nov 26 '20 at 19:17
  • 2
    @fps thanks this is very nice quesiton. let to others share idea – user3661613 Nov 26 '20 at 19:36
  • I have no idea of where you got the time restriction from, or why anyone thinks it matters. But it certainly does NOT matter to the easy `O(k log(k))` solution or the tricky `O(k)` one. See https://www.sciencedirect.com/science/article/pii/S0890540183710308 for the `O(k)` solution. – btilly Dec 07 '20 at 19:13
  • @btilly would you please show a bit detail on O(K)? if not please provide your logic of O(k log k) method as an answer. share your expertness to others... especially beginner like me. – user3661613 Dec 07 '20 at 19:27
  • 2
    @user3661613 Sorry, but no. What I have to say about the `O(k log(k))` solution is already said at geeksforgeeks. I have nothing I wish to add about the `O(k)` solution that I did not say 3 years ago at https://stackoverflow.com/a/47894452/585411. In particular I'm not willing to do the work to implement that paper and explain how it works. – btilly Dec 07 '20 at 20:28
  • :) @btilly thanks so much. I think you implement it. if you are so expert you can implement it. but not some beginner like me. anyway I want a logical reason why (k <= Sqrt (P)) cannot affect the solution ? – user3661613 Dec 07 '20 at 20:40
  • 1
    This has been discussed [over at COMPUTER **SCIENCE** @SE](https://cs.stackexchange.com/a/54067), too. – greybeard Dec 07 '20 at 21:25
  • 1
    If you want an expert to do something, you should be prepared to pay that expert's contracting rates. The last time I contracted was a few years back at $150/hour. I'm not sure up front how many hours this one would take. As for the logical reason, there might be some special solution that imposes that restriction. But the fact that there is a general solution that is provably optimal without that restriction means that the special solution cannot be more than a constant factor faster. – btilly Dec 07 '20 at 22:37

0 Answers0