Heap Sort

Heap Sort is a comparison-based sorting algorithm that leverages the properties of a binary heap. A binary heap is a complete binary tree that satisfies the heap property - in a max heap, for any given node i, the value of i is greater than or equal to the values of its children. Conversely, in a min heap, the value of i is less than or equal to the values of its children. The Heap Sort algorithm uses this structure to sort an array in ascending or descending order.

How it works

Heap Sort primarily involves two steps - building the heap and then performing the sort operation.

1. Building the heap: The initial unsorted array is transformed into a heap data structure. For sorting in ascending order, a max heap is built, whereas for sorting in descending order, a min heap is constructed. The heap construction is performed in-place, i.e., the data structure is built within the array itself.
2. Performing the sort: Once the heap is constructed, the root of the heap (which is the maximum or minimum element, depending on the type of heap) is swapped with the last element of the heap. The size of the heap is then reduced by one. The swapping operation may disrupt the heap property, so the heapify operation is performed to restore it. This process is repeated until the heap size reduces to 1, resulting in a sorted array.

The crux of Heap Sort lies in the heapify operation which maintains the heap structure after each swap.

Here is a simple implementation in C#:

public void HeapSort(int[] arr)
{
    var n = arr.Length;

    for (var i = n / 2 - 1; i >= 0; i--)
    {
        Heapify(arr, n, i);
    }

    for (var i = n - 1; i >= 0; i--)
    {
        Swap(ref arr[0], ref arr[i]);
        Heapify(arr, i, 0);
    }
}

private void Heapify(int[] arr, int n, int i)
{
    var largest = i;
    var left = 2 * i + 1;
    var right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
    {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest])
    {
        largest = right;
    }

    if (largest != i)
    {
        Swap(ref arr[i], ref arr[largest]);
        Heapify(arr, n, largest);
    }
}

private void Swap(ref int a, ref int b)
{
    (a, b) = (b, a);
}

In the provided code, the first phase of the sort function builds a max heap from the given array. This is done by calling the Heapify method for each of the non-leaf nodes, starting from the lowest and rightmost node that has children (the mid-element of the array).

In the second phase, the root node (the maximum element in a max heap) is repeatedly removed, swapped with the last element of the reduced heap (the element at the end of the array), and then the heap property is restored by calling Heapify again.

Time complexity

From a time perspective, Heap Sort has a complexity of O(n log n), both in the average and worst-case scenarios. This time efficiency is due to the fact that you have to perform n heapify operations, each of which has a complexity of O(log n).

Space complexity

In terms of space, Heap Sort is very efficient, with a complexity of O(1). This is because all the sorting happens in place, i.e., within the original array, without the need for additional space.

Conclusion

Heap Sort is a very powerful sorting algorithm that takes advantage of the unique properties of a binary heap data structure. Its efficiency in terms of time complexity makes it a preferred choice for sorting large datasets. In contrast, its in-place sorting feature makes it an excellent choice in environments where memory usage is an issue.

References

• Algoritmi e programmazione in C di Francesco Oliveri, Aracne editrice (Italian book)