0
$\begingroup$

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.

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

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..

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You can use a loop, as long as the loop does at most a fixed number of rounds. $\endgroup$ – vonbrand Apr 15 at 22:49
  • $\begingroup$ Will it work with MIN HEAPS? isnt that algorithm will work at constant time for MAX HEAPS? $\endgroup$ – Alon Apr 16 at 0:18
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.