# Heaps and Heapsort - Find the 7'th biggest value in a min heap by $O(1)$

I have a min heap.

I need to find the 7'th biggest value in the heap with $$O(1)$$.

I need to build the algorithm.

I dont realy have an idea how to get to this efficiency.

Help?

Thanks.

• A min-heap is a heap with the least element as root? I believe the naming isn't standard. – vonbrand Apr 16 '20 at 21:40

I am pretty sure that you cannot solve this problem in $$O(1)$$ time without additional assumptions. You have to scan at least $$L-6$$ leaves (which already gives you $$\Omega(n)$$ time complexity), where $$L$$ is a total number of leaves in a heap, to find an answer. Indeed, suppose that you have an algorithm which solves the problem and scans less than $$L-6$$ leaves for some input heap. Then you can pick 7 arbitrary non-scanned leaves and increase their values such that one of them will become the 7-th biggest in the heap. But the repeated run of your algorithm on the modified heap won't scan the 7 modified vertices (because it didn't scan it during the first run and all other vertices remained unchanged) and, consequently, won't find the correct answer for this heap.