Heap Sort Sortdown §

Most of the work during heapsort is done during the second phase, where we remove the largest remaining items from the heap and put it into the array position vacated as the heap shrinks.

Working of Heap Sort §

• Since the tree satisfies Max-Heap property, then the largest item is stored at the root node.
• Swap: Remove the root element and put at the end of the array (nth position) Put the last item of the tree (heap) at the vacant place.
• Remove: Reduce the size of the heap by 1.
• Heapify: Heapify the root element again so that we have the highest element at root.
• The process is repeated until all the items of the list are sorted.

The code below shows the operation.

// Heap sort
for (int i = n - 1; i >= 0; i--) {
  swap(&arr[0], &arr[i]);
  // Heapify root element to get highest element at root again
  heapify(arr, i, 0);
}