CODEWITHSUNDEEP
algorithmsortingheap
JAN
JAN

Reputation: 21885

Build a sorted list from a maximum heap in O(n * log(log(n)))?

I have a maximum heap represented in an array A , and I have the following question :

Is it possible to build a sorted list , based on the maximum 
heap - A - in O(n*log(log(n))) ?

My answer : No we can't ! we can always run on A and execute MergeSort in O(n*log(n)) or a QuickSort in O(n*log(n)) (worst case O(n^2)) .

I thought also maybe to build the actual heap based on A , this would take O(n) , and then extract from there all the elements in O(n*log(n)) , but I gained nothing here .

At the moment I can't see any option for O(n*log(log(n))) , any ideas ?

Upvotes: 1

Views: 466

Answers (2)

Justin
Justin

Reputation: 4216

If you have a max-heap in an array form then using something like insertion sort on that array should yield pretty good results. A max heap in array form is nearly sorted (descending) and the best case for insertion for is O(n) when the array is nearly sorted. It'll still has a O(n^2) worst case but I don't think you'd ever hit the worst case.

Upvotes: 2

Pashok
Pashok

Reputation: 157

I think it's not possible: There is an algorithm to build a max-heap in o(n) (look here Is there a O(n) algorithm to build a max-heap?) So if you could make a heap in o(n) and then sort it in o(nlog(log(n)), you could get a sort algorithm that works in o(nlog(log(n)), which is not possible if you got no initial information about your input.

Upvotes: 6

Related Questions