title: Lower bound on heapsort?
body: <p>It's well-known that the worst-case runtime for heapsort is &Omega;(n lg n), but I'm having trouble seeing why this is.  In particular, the first step of heapsort (making a max-heap) takes time &Theta;(n).  This is then followed by n heap deletions.  I understand why each heap deletion takes time O(lg n); rebalancing the heap involves a bubble-down operation that takes time O(h) in the height of the heap, and h = O(lg n).  However, what I don't see is why this second step should take &Omega;(n lg n).  It seems like any individual heap dequeue wouldn't necessarily cause the node moved to the top to bubble all the way down the tree.</p>
  
  <p>My question is - does anyone know of a good lower-bound proof for the best-case behavior of heapsort?</p>