CODEWITHSUNDEEP
max-heap
user2853207
user2853207

Reputation: 21

How is the time complexity of creating a max heap O(n)

How is the time complexity of creating a max heap O(n). Is it that the child node will compare with its parent in only O(i) or is it O(log n).

Upvotes: 1

Views: 1373

Answers (1)

Srinivasan Subbiah
Srinivasan Subbiah

Reputation: 56

a. The complexity is O(n) in case when we do the sorting using bubble down approach.

Idea here is heap is built by blindly inserting the elements into the array and then start correcting/swapping the dominance violations using bottom up approach. Advantage: We have n/2 leaf nodes which does not require any bubble down as they obey the dominance automatically. Then we move to the internal parents and compare it with its children. If violation is there then swap/bubble down. Then move to higher parents and so on Even the internal(parent) nodes require swapping in correspondence to the height of the level they are in. n/2 are leaves. n/4 are at height 1, n/8 are at height of 2...leading to the cost of building the heap to the following equation.(Max Height:lg n)

Summation from 0 to lg n: (n/2^h+1)h

Which boils down to approx. 2n

Hence the Time Complexity is O(n).

b. Comparison happens only with the children for a given parent level.

Hope it answered your questions

Upvotes: 1

Related Questions