Heap Sort

Heap Sort is an efficient sorting algorithm that leverages a data structure called Binary Heap to organize and sort data. It works by first building a heap from the data and then repeatedly extracting the largest (or smallest) element from the heap and rebuilding the heap until all elements are sorted. This method is known for its reliable performance and in-place sorting capabilities, making it a strong choice for handling large datasets without requiring extra memory.

Things to Observe

• Building the Heap: The first phase of the algorithm rearranges the array into a Max Heap, where the element at the root of any sub-tree is the largest.
• Extracting the Max: In the second phase, watch how the largest element (at the root) is repeatedly swapped with the last element of the heap, and the heap is rebuilt. This process gradually builds the sorted array from the end.

Pseudocode

function heapify(i):

    largest = i

    left = 2 * i + 1

    right = 2 * i + 2

    if left < n:

        if arr[left] > arr[largest]:

            largest = left

    if right < n:

        if arr[right] > arr[largest]:

            largest = right

    if largest != i:

        swap(i, largest)

        heapify(largest)

for i = (n / 2 - 1) down to 0:

    heapify(i)

for i = n - 1 down to 1:

    swap(0, i)

    heapify(0)