CODEWITHSUNDEEP
algorithmmax-heap
user21312
user21312

Reputation: 143

Find the 10-th largest elements of a Max-Heap in O(1) time

I'm trying to implement an algorithm to find the 10-th largest elements of a Max-Heap with n distinct elements in O(1) time.

I tried to draw it and using the heap property but it gets more and more complicated as I go deeper in the heap. This is a draft I made and where I'm stuck at - From the fact that we have distinct elements and the heap property we know that the parent is always greater than its children. Therefore the root is the maximal element. The next maximal element is the greater element between the root's sons.

Edit: I also thought about comparing between the sons of the greater one to the other parent. If at least one of them is greater than the other parent, by the heap property we continue from the maximal sons and keep doing it till we have 10 elements but it's not always true because there might be no elements as we go deeper and now we need to go back all over again.

Any explanation or even Pseudo-code will be much appriciated.

Thanks in advance!

Upvotes: 0

Views: 1519

Answers (1)

Henry
Henry

Reputation: 43798

One possible solution, most likely not the fasted, but still O(1) would be to extract all the top elements of the heap (viewed as a tree) down to a level of 10. Then sort them and return the tenth element.

Note, that the number of extracted elements is bounded which leads to the O(1) effort.

Upvotes: 1

Related Questions