# Where is knowing the 2^k largest elements in a array useful?

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.

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

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.