Geek asks and answers

Looking for the 7th largest item in the max heap?

So my friend and I do not see the eye in this matter. Does it specify the time complexity of searching for the 7th largest element in the max heap of n elements?

I believe that it should be O (n), and she believes that it should be O (1). My logic is that let n be 7, then the 7th largest element will be the last element in the heap, so if we look at the worst case, then it should be O (n). She, however, says that since this is the maximum heap, so finding the 7th largest element should take constant time. But using its logic, even the 50th largest element or 100th largest element can be found O (1) times. Also in the book in which we came across this issue, it says that the solution is O (logn).

Can someone tell me which solution is right?

+3
source share
3 answers

There is a solution O (1). Suppose the heap is representative as a tree, and max is the root. Than the distance between the node with the 7th largest element, and the root is less than or equal to 6. The number of nodes with a distance to the root <= 6 never exceeds 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127. This is a constant. They can go through constant time.

+4
source

A simple algorithm that finds the seventh largest element in the maximum heap,

repeat 6 times:
    del-max(heap)
return max(heap)

del-max, O (lg n). max . del-max , O (lg n). , .

+5

There is an O (k) algorithm for selecting the kth element in a heap of size n, where n → k. See Optimal Algorithm for Choice in the Mini-Heap , Greg Frederickson.

You can download PDF from this page (link in the upper left corner).

So the answer is that you, your friend, and the book you are reading are wrong.

+3
source

More articles:


All Articles