Formation of Binary Heaps using Arrays Shortcut

62 views Asked by At

If we arrange array in ascending order, then we'll get Binary Heap. Is there any drawback of this advantage. If yes then what will be the reason of that?

1

There are 1 answers

2
sameerkn On

"Arranging array in ascending order, then we'll get Binary Heap". This is correct. Now it depends upon which algorithm you use to sort the array in ascending order. Best Sorting Algorithm perform with complexity O(NLogN).

While the algorithm Build_Heap to just create a binary heap has complexity of O(N).

Unless and until you use non-comparison based sorting method like Counting Sort your complexity for creating binary heap will be atleast O(NLogN) and atmost O(N^2).

So traditional method of creating binary heap is favorable.

Although Counting Sort will take O(N) time but it will require extra space O(N), while traditional Build_Heap will be create binary heap in-place.