Heap Sort: Theory, Visualization, Implementation, and Complexity Analysis

1. Introduction

Heap sort is a comparison‑based sorting algorithm that first builds a max‑heap from the input array A[1..n] so that the largest element is at the root (A[1]). The algorithm repeatedly swaps the root with the last element of the unsorted portion and restores the heap property.

2. Theory

Given an input list A[1..n] (n = len(A)), the max‑heap ensures each parent node is not smaller than its children. The sorting steps are: swap A[1] with A[n], re‑heapify the remaining A[1..n‑1]; repeat until the array is in non‑decreasing order.

3. Visual illustration

The article describes building the max‑heap bottom‑up (similar to building a min‑heap) and shows step‑by‑step diagrams for a 10‑element example, swapping the root with the rightmost leaf, restoring heap order, and continuing until the sorted array is obtained.

4. Implementation

<code>def __down_heap(arr, num, j):
    """Ensure arr[0:num] satisfies heap property for node j."""
    left = 2 * j + 1  # left child index
    right = 2 * j + 2  # right child index
    if left < num:
        large_child = left
        if right < num:
            if arr[right] > arr[left]:
                large_child = right
        if arr[large_child] > arr[j]:
            arr[large_child], arr[j] = arr[j], arr[large_child]
            __down_heap(arr, num, large_child)

def heapify(arr):
    """Build a max‑heap from the list."""
    for j in range((len(arr) - 1) // 2, -1, -1):
        __down_heap(arr, len(arr), j)

def heap_sort(arr):
    """Perform heap sort."""
    heapify(arr)  # build max‑heap
    for i in range(len(arr) - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # move current max to end
        __down_heap(arr, i, 0)  # restore heap for the reduced array

if __name__ == '__main__':
    arr = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
    heap_sort(arr)
    print(arr)
</code>

5. Complexity analysis

Time complexity consists of O(n) for building the heap and O(n log n) for the successive heap‑adjustments, giving a worst‑case time of Θ(n log n). The algorithm sorts in place; aside from the input array itself, it uses only a constant amount of extra memory, so the space complexity is Θ(n) when counting the input size (Θ(1) additional auxiliary space).