- #1

fiksx

- 77

- 1

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 4the 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!

https://www.growingwiththeweb.com/data-structures/binary-heap/build-heap-proof/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 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 4the 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!

https://www.growingwiththeweb.com/data-structures/binary-heap/build-heap-proof/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}})

Last edited by a moderator: