Heap Sort

• Restore-Heap(i): $O(h)$ where $h$ is the height of the node i.
  
  
  
  
  
  
  
  
  
  
  
  
  
• Construct Heap:
  For $i = \left \lfloor \frac n 2 \right \rfloor$ down to 1 Restore-Heap(i)
  $O(n)$
  
  
  
  
  
  
  
  
  
  
  
  
  
• Heap Sort:
  
  1. Construct Heap - $O(n)$
  2. For $i$:=$n$ down to $2$- $O(n\log n)$
     exchange $L[1]$ with $L[i]$
     decrement heap size
     Restore-Heap($1$)
• Time Complexity of deletion phase in Heap Sort
  
  $$\begin{eqnarray*} W(n)& =& 2 \log n+W(n-1)\\ &=&2\sum_{i=1}^{n}\log i\\ &\l... ...] &=&\left[2(x\log x-x) \right]_{1}^{n+1}\\ &=& 2n \log n-2n \end{eqnarray*}$$