2
$\begingroup$

I came across this question today on stackoverflow. It asks:

Find the largest, $2$nd, $4$th, $8$th, ..., $2^{\log n}$-th largest element in an arrary. Use $O(n)$ algorithm. $2^k$

I've come across this before and know how it can be done, but I've been been trying to find examples of algorithms that incorporate the above into the actual algorithm for a while now since I'm curious about how it can be used in practice. However, I haven't had any luck at looking this up online haven't had any results. Therefore, I'm asking if anyone knows a formal name for an algorithm that solves the above or some examples of algorithms that use the above in some way or another.

$\endgroup$
  • 2
    $\begingroup$ This looks like an exercise in algorithm design. It isn't necessarily applied in practice. $\endgroup$ – Yuval Filmus Oct 1 '14 at 3:32
4
$\begingroup$

If you implement a solution to the problem in an obvious way using quickselect with partitioning ($\log_2 n$ selects, with the $i$th one costing $n/(2^i)$), you will end up with an array partitioned in such a way that it is essentially Williams's binary heap.

$\endgroup$
  • $\begingroup$ Interesting, a heap of sorts does match my own testing/research which did make use of an in-place quickselects. $\endgroup$ – Nuclearman Oct 3 '14 at 17:36

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.