0
$\begingroup$

Say we have a Priority Queue of size 1000 that is implemented using Max Heap.

Now if i want to get the top 5 elements, the most laid back method is to poll the maximum 5 times, resulting in a set of five maximum numbers. The complexity of a poll function using heap is Log N. Hence, retrieving 5 top values or say, K top values will result in complexity KLogN.

Is there any other way of getting the top K values using priority queue with lesser complexity?

The solution Find k maximum numbers from a heap of size n in O(klog(k)) time seems to increase the complexity rather than decreasing it, which is why i am trying to think about some other logic. there is a sort function in the logic which will itself consume kLogk for finding one. hence say, for 5 items..it will be k*(kLogK) if K=5? hence, its not decreasing complexity.

Improve this question
$\endgroup$
7
  • $\begingroup$ Do you care about the order of those K top values? Do they have to be in decreasing order? Or do you just want the set, without regard to order? $\endgroup$
    – D.W. ♦
    Commented Feb 22, 2018 at 7:18
  • $\begingroup$ i just want the entire set. order is not a priority. but if ordering lessens the complexity, i am fine with it as well $\endgroup$
    – Saurav
    Commented Feb 22, 2018 at 7:30
  • 1
    $\begingroup$ $k\log k<k\log N$. Why do you think the $O(k\log k)$ solution increases the complexity? $\endgroup$
    – xskxzr
    Commented Feb 22, 2018 at 12:12
  • $\begingroup$ That question asks for an algorithm with $O(k\log k)$ complexity, and that's why your question is a duplicate of that question. The algorithm the OP in that question gives may not be correct, but that does not matter, because answers to that question should correct it or propose a new solution. If you are not satisfied with already existed answers, you can make that question draw attention to our users, but you should not ask the question again. $\endgroup$
    – xskxzr
    Commented Feb 26, 2018 at 11:26
  • $\begingroup$ I don't understand why you think that an $O(k \log k)$-time algorithm increases the complexity (from what to what? $O(k \log N)$ to $O(k \log k)$ is a decrease, not an increase). Basically, I can't understand the last paragraph of the question. An $O(k \log k)$-time algorithm would be an answer to your question (i.e., a way of getting the top $k$ values with lesser complexity). If you think this is not a duplicate, you'll need to edit the question to clarify what your question is and why that other question is not a solution, in a way that the rest of us can understand. $\endgroup$
    – D.W. ♦
    Commented Feb 26, 2018 at 17:15

0

Reset to default