CODEWITHSUNDEEP
javamaxheap
Henry
Henry

Reputation: 574

Time complexity of getting max value from Min Priority Queue backed by a Heap

I ran into a question online asking for the average time complexity of getting the maximum value from a Min Priority Queue backed by a Heap.

I reasoned the answer to be O(n) because a heap is backed by an array, and iterating through the array once to find the maximum would take n comparisons.

However, the answer is O(nlogn). Can anyone explain why this is the case and where my reasoning fails?

Upvotes: 0

Views: 1351

Answers (1)

user5063151
user5063151

Reputation:

A heap can be backed by an array (if you choose to implement it that way). As most programming languages have arrays, it makes sense to do so. But from the outside, we cannot assume that.

And yes, technically, you can find the max value in linear time If you have access to the array, which you will not. Example...in Java, do you have access to the dynamically sized array behind the ArrayList class? No, because Java does not want you to mess it up!

Assuming that you can only use the public methods / attributes exposed by the Heap class...You are more than likely not going to have access to that array. If that array were publicly available, it can be easily manipulated, and the Heap structure could be easily compromised.

I think the question assumes that you would use the Heap's methods. And in a min heap, the max value would come out at the end (heapsort), which would require n calls to the remove() function, which is O(logn), so n * log(n) implies that the heapsort is O(n*logn).

In short, the question is asking the time complexity of heap sort.

Upvotes: 2

Related Questions