[Home Page - Algorithms](/@roger61205/Algorithms) [toc] [Introduction to Heap](/SEMyQ563R8qE7q8mrYpvXw) # Max-Heap ## Algorithm ### `BUILD-HEAP` ![image](https://hackmd.io/_uploads/HJ_r7pY1A.png) ### `HEAPIFY` `HEAPIFY` is used to maintain the heap property. ![image](https://hackmd.io/_uploads/SyYVmpY1C.png) :::info ![](https://i.imgur.com/4B54WC4.png) ::: ### `HEAPSORT` ![image](https://hackmd.io/_uploads/H1DIQptyC.png) ## Analysis ### Time Complexity #### `BUILD-HEAP` A heap has less or equal to $\lceil\frac{n}{2^{k+1}}\rceil$ nodes of height $h$ and the height is $\lfloor logn\rfloor$. The time required by `HEAPIFY` when called on a node of height $h$ is $O(h)$, so the total cost of `BUILD-HEAP` is $$ \sum_{h=0}^{\lfloor logn\rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h)=O(n\sum_{h=0}^{\lfloor log_2n\rfloor}\frac{h}{2^h}) $$ Because $$ \sum_{h=0}^\infty\frac{h}{2^h}=2 $$ The time complexity of `BUILD_HEAP` is $$ O(n) $$ #### `HEAPIFY` $$ O(logn) $$ #### `HEAPSORT` 1. `BUILD-MAX-HEAP`: $O(n)$ 2. `MAX-HEAPIFY`: $O(logn)$ for $n-1$ times Overall: $O(nlogn)$ **reference** NCKUCSIE 1112_F721300 Algorithms [Heapsort Algorithm | Interview Cake](https://www.interviewcake.com/concept/java/heapsort) Introduction to Algorithms (Third Edition), T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein