---

Algorithm for Heap Sort

---

Step 1: [Build Heap H] 
        Repeat for I= 0 to N-1 
          CALL Insert_Heap(ARR, N, ARR[I]) 
        [END OF LOOP] 
Step 2: (Repeatedly delete the root element) 
        Repeat while N > 0 
          CALL Delete_Heap(ARR, N, VAL) 
          SET N= N+1 
        [END OF LOOP] 
Step 3: END

How Heap Sort Works

• Initially on receiving an unsorted list, the first step in heap sort is to create a Heap data structure (Max-Heap or Min-Heap).
• Once heap is built, the first element of the Heap is either largest or smallest (depending upon Max-Heap or Min-Heap), so we put the first element of the heap in our array.
• Then we again make heap using the remaining elements, to again pick the first element of the heap and put it into the array.
• We keep on doing the same repeatedly until we have the complete sorted list in our array.

---