2

I cant understand something about heap.

The children’s subtrees each have size at most 2n/3—the worst case occurs when the bottom level of the tree is exactly half full

" the worst case occurs when the bottom level of the tree is exactly half full. "

I cant understand this. why half full?.. why? I think it may take more time if there are more tree. or take less time otherwise.

thank you for reading

Oleg Estekhin
  • 8,063
  • 5
  • 49
  • 52
user3528211
  • 87
  • 5
  • This has been answered already. http://stackoverflow.com/questions/6859514/worst-case-in-max-heapify – Shifty Apr 19 '15 at 02:18

2 Answers2

2

heapsort time order depends on the depth of the tree, so if you have a tree with n nodes and if it's balanced (means the number of nodes in each children's subtrees is almost equal) it is the best case because of least possible depth! if the tree is not balanced its the worst case and the depth of the tree increases.. if you have a tree with n nodes and the "bottom level of the tree is half full" it increases the depth of the tree and increases the order that way...

ameerosein
  • 523
  • 3
  • 16
1

While heapify we compare subroot with its children's. In case of build heap the n-2n/3 nodes are leaf node so we start heapify process from 2*n/3 node in order to avoid unnecessary iterations

dead programmer
  • 4,223
  • 9
  • 46
  • 77