Searching the 7th largest element in a max-heap?

Question

So my friend and I are not seeing eye to eye in this question. It asks for the time complexity of searching for the 7th largest element in a max-heap of n elements?

I'm of the opinion that it should be O(n) and she is of the opinion it should be O(1). My logic is that suppose n is 7 then 7th largest element will be the last element in the heap so if we consider the worst case it should be O(n). She however says that since it's a max heap so finding the 7th largest element should take constant time. But using her logic even the 50th largest element or the 100th largest element can be found in O(1) time. Also the book in which we came across this question says the solution will be O(logn).

Can someone please tell me which solution is correct?

Answer 1

There is an O(1) solution. Let's assume that the heap is represnted as a tree and max element is a root. Than the distance between the node with 7-th largest element and the root is less than or equal to 6. The number of nodes with distance to the root <= 6 is never greater than 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127. It is a constant. They can traversed in constant time.

Answer 2

The simple algorithm that finds the seventh-largest element in a max heap is

repeat 6 times:
    del-max(heap)
return max(heap)

The first loop performs a constant number of del-max operations, each taking O(lg n) time. The max operation takes constant time. The del-max operations dominate, leading to a total O(lg n) complexity. I'm not claiming this is optimal.

Answer 3

There is an O(k) algorithm for selecting the kth element in a heap of size n, where n >> k. See An Optimal Algorithm for Selection in a Min-Heap, by Greg Frederickson.

You can download the PDF from that page (link in the upper left).

So the answer is that you, your friend, and the book you're reading are all wrong.