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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
O(1) means: You need to do this with a fixed number of operations. Basically, write code without a loop. That's not difficult. It's a lot of code, but a fixed amount of code.
Look at your heap as if it was a binary tree. You want the 7th largest item in your tree. That's the sixth largest of the subtrees L and R. If the item at L is smaller than the item at R, it's the fifth largest item in the subtrees L, RL and RR, otherwise the fifth largest item in the subtrees R, LL and LR. And so on..
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.