[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