- 61

- 0

I'm trying to count running time of build heap in heap sort algorithm

The basic idea behind why the time is linear is due to the fact that the time complexity of heapify depends on where it is within the heap. It takes O(1)O(1)O(1) time when the node is a leaf node (which makes up at least half of the nodes) and O(logn)O(\log n)O(logn) time when it’s at the root.

The O(n)O(n)O(n) time can be proven by solving the following:

##\sum_{h=0}^ {\lfloor lg n \rfloor} \frac{n}{2^{h+1}}O(h)=O(n\sum_{h=0}^ {lg n}\frac{h}{2^{h}})##

suppose this is the tree

4 .. height2

/ \

2 6 .. height 1

/\ /\

1 3 5 7 .. height 0

what I understand here $O(h)$ means worst case for heapify for each node, so height=ln n if the node is in the root for example to heapify node 2,1,3 it takes $ln_2 3 =1.5$ the height of root node 2 is 1, so the call to HEAPIFY is $ln_2 n=height = O(h)$

im not sure about this $$\frac{n}{2^{h+1}}$$ , is the number of nodes for any given height , suppose height is 1 and sum of nodes is 3 such as 2,1,3, so ##\frac{n}{2^{h+1}}= \frac{3}{2^{0+1}}=1.5=2## , when height is 0 there is at most two nodes. am i correct?

suppose given height is 0 so it is the last layer, then when sum of nodes is 7 , ##\frac{n}{2^{h+1}}## =##\frac{n}{2^{0+1}}=\frac{7}{2}=3.5=4? ## -> {1,3,5,7} if the root is 4

the summation is lg n because it sum the total height when it do heapify?

and last is to count the big-oh, BUILD HEAPIFY will call HEAPIFY ##\frac{n}{2}## times, and each will be ##ln_2 n## = height of the root, so ##\frac{n}{2} * ln_2 n##?

please correct me if i am wrong thanks!

this is the reference i used, and also i read about this in CLRS book

[1]: https://i.stack.imgur.com/KYOjp.png

[2]: https://www.HostMath.com/Show.aspx?Code=\sum_{h=0}^ {\lfloor lg n \rfloor} \frac{n}{2^{h+1}}O(h)=O(n\sum_{h=0}^ {lg n}\frac{h}{2^{h}})

Code:

```
BUILD-HEAP(A)
heapsize := size(A);
for i := floor(heapsize/2) downto 1
do HEAPIFY(A, i);
end for
END
```

The O(n)O(n)O(n) time can be proven by solving the following:

##\sum_{h=0}^ {\lfloor lg n \rfloor} \frac{n}{2^{h+1}}O(h)=O(n\sum_{h=0}^ {lg n}\frac{h}{2^{h}})##

suppose this is the tree

4 .. height2

/ \

2 6 .. height 1

/\ /\

1 3 5 7 .. height 0

what I understand here $O(h)$ means worst case for heapify for each node, so height=ln n if the node is in the root for example to heapify node 2,1,3 it takes $ln_2 3 =1.5$ the height of root node 2 is 1, so the call to HEAPIFY is $ln_2 n=height = O(h)$

im not sure about this $$\frac{n}{2^{h+1}}$$ , is the number of nodes for any given height , suppose height is 1 and sum of nodes is 3 such as 2,1,3, so ##\frac{n}{2^{h+1}}= \frac{3}{2^{0+1}}=1.5=2## , when height is 0 there is at most two nodes. am i correct?

suppose given height is 0 so it is the last layer, then when sum of nodes is 7 , ##\frac{n}{2^{h+1}}## =##\frac{n}{2^{0+1}}=\frac{7}{2}=3.5=4? ## -> {1,3,5,7} if the root is 4

the summation is lg n because it sum the total height when it do heapify?

and last is to count the big-oh, BUILD HEAPIFY will call HEAPIFY ##\frac{n}{2}## times, and each will be ##ln_2 n## = height of the root, so ##\frac{n}{2} * ln_2 n##?

please correct me if i am wrong thanks!

### Binary heap: Build heap proof

The binary heap data structure supports a build heap operation that runs in O(n). Intuitively it might seem that it should run in O(n \log n) time since it performs an O(\log n) operation n/2 times. This article provides a proof of the linear run time.

www.growingwiththeweb.com

[1]: https://i.stack.imgur.com/KYOjp.png

[2]: https://www.HostMath.com/Show.aspx?Code=\sum_{h=0}^ {\lfloor lg n \rfloor} \frac{n}{2^{h+1}}O(h)=O(n\sum_{h=0}^ {lg n}\frac{h}{2^{h}})

Last edited by a moderator: