Algorithm to identify top $\log n$ elements in $O(n)$ time Airlines has a new policy to give a first-class upgrade coupon to their customers based on the number of miles accumulated. They decided to give it to their top $\log(n)$ frequent flyers, where n is the total number of the airlines’ frequent flyers. Their current algorithm runs in $O(n \log(n))$ time to sort the flyers scan the sorted list to pick the top logn flyers. Describe an algorithm that identifies the top $\log(n)$ flyer in $O(n)$ time.

How can I devise an algorithm for this problem? I tried to solve it with priority queue ADT and some well-known sorting, but cannot solve this problem.
For every $k$, you can find the $k$th largest element in $O(n)$, using a linear time selection algorithm. You can then find the $k$ largest elements by scanning the array.