CODEWITHSUNDEEP
data-structuresmaxtime-complexityheapmax-heap
Amen
Amen

Reputation: 1633

Most Efficient Way to find the logn th Maximum in a Max Heap

The title says it all; What is the most efficient way to find the log nth maximum number in a max heap with n elements?
ps: The text book I'm reading vaguely explained a solution with time complexity of O(lognloglogn) by using another heap that I can't understand, can we do better than that?

Upvotes: 0

Views: 1000

Answers (1)

blazs
blazs

Reputation: 4845

Let H be the original max-heap. Let H' be another max-heap, initially empty, that operates on pairs (index, value) of elements from the first heap and orders the pairs based on the second component.

  1. H'.push(0, H[0])
  2. count = ceil(log n)
  3. while count > 0 do
    1. (i, v) := H'.extract-max() // takes O(log log n) time
    2. H'.push(2i+1, H[2i+1]) if H[2i+1] exists // O(log log n) time
    3. H'.push(2i+1, H[2i+2]) if H[2i+2] exists // O(log log n) time
    4. count := count - 1
  4. return v

The reason we have O(log log n) bounds on running times of operations of H' is that H' contains at most log n elements and each operation runs in time logarithmic in the number of elements of the heap, which is O(log log n).

The total running time is obviously O(log n log log n). I'm assuming the original max-heap H is represented with an array.

Upvotes: 1

Related Questions