CODEWITHSUNDEEP
performancealgorithmsortingtimeheap
CHEN Sai
CHEN Sai

Reputation: 29

Why does BUILD-MAX-HEAP take time O(n) while HEAP-SORT takes O(nlgn) time?

While I am reading "Introduction to Algorithms", I was wondering why HEAPSORT takes time O(nlgn), whereas BUILD-MAX-HEAP takes time O(n).

The HEAPSORT begins its for loop at A.length downto 2, calling MAX-HEAPIFY.

The BUILD-MAX-HEAP begins its for loop at the floor of A.length/2 downto 1, calling MAX-HEAPIFY.

The MAX-HEAPIFY takes time O(lgn). I was wondering what causes BUILD-MAX-HEAP more faster than HEAPSORT.

Upvotes: 1

Views: 1721

Answers (2)

gnasher729
gnasher729

Reputation: 52632

In the heapsort algorithm, you always worry about the "heap condition" which states that no element should be placed in the heap above a greater element, and if there is such an element violating the heap condition, then you fix it. How much effort it takes to fix the heap condition depends on how high above the bottom the element is that needs fixing.

In the inital phase where the heap is built, the last half of the elements don't violate the heap condition because there is nothing below. One quarter of the elements violate the heap condition, but are just one row above the bottom of the heap, so only one step is needed to fix the heap condition. Then one eighth of the elements violate the heap condition, but are just two rows above the bottom of the heap, so only two steps are needed.

If you add up the number of steps needed, you get n/4 * 1 + n/8 * 2 + n/16 * 3 + n/32 * 4 ... which adds up to less than n. But when you then sort by repeatedly putting the first element with the largest number at the end of the array, the heap condition is always violated at the top of the heap, (log n) rows above the bottom, so log n steps are needed to fix the heap condition.

Upvotes: 1

Mike
Mike

Reputation: 735

In building a heap, we always "HEAPIFY" the element starting from the bottom, but when sorting it, we always "HEAPIFY" the top most element. In both the case, the height is varying but point to note:

*In building a heap, maximum elements which we heapify lie at the bottom and they get very less height to heapify hence O(n), but while sorting we always heapify top most element. Even though the height is decreasing it is not as advantageous as in the prior case. *

I hope you understand what I'm trying to say.

Upvotes: 1

Related Questions