Algorithm – search for the 7th largest element in the largest heap?

So my friend and I don't agree on this issue It requires the time complexity of searching the 7th largest element in the maximum heap of n elements?

I think it should be o (n) and she thinks it should be o (1) My logic is to assume that n is 7, and then the seventh largest element will be the last element in the heap, so if we consider the worst case, it should be o (n) However, she said that because it is the largest heap, it should take constant time to find the seventh largest element But using her logic, you can even find the 50th or 100th element in O (1) time Our book on this problem also says that the solution is O (logn)

Can someone tell me which solution is right?

Solution

There is an O (1) solution We assume that the heap is rebuilt as a tree, and the max element is the root The distance between the node with the 7th largest element and the root is less than or equal to 6 The number of nodes from the root < = 6 will never be greater than 1 2 4 8 16 32 64 = 127 This is a constant They can travel in a constant time