Heap Sort is an efficient sorting algorithm that leverages the properties of a heap data structure. A heap is a complete binary tree where each parent node is greater than or equal to (max-heap) or less than or equal to (min-heap) its child nodes. Heap sort repeatedly extracts the maximum element (root) and adjusts the heap, resulting in a sorted array. It has a stable time complexity of O(n log n) and is suitable for large-scale data sorting.

Heap Structure and Index Relationships¶

A heap can be represented as an array using a complete binary tree. If the array indices start from 0:
- For a parent node at index i, the left child is at 2i + 1 and the right child at 2i + 2.
- For a child node at index j, the parent node is at (j - 1) // 2.

Core Operation 1: Heapify¶

Heapify adjusts a subtree rooted at index i to maintain the max-heap property. Steps:
1. Assume the current node i is the largest.
2. Compare i with its left and right children to find the largest.
3. If the largest child is greater than i, swap them and recursively heapify the affected subtree.

def heapify(arr, n, i):
    largest = i  # Assume current node is the largest
    left = 2 * i + 1
    right = 2 * i + 2

    # Update largest if left child is larger
    if left < n and arr[left] > arr[largest]:
        largest = left
    # Update largest if right child is larger
    if right < n and arr[right] > arr[largest]:
        largest = right

    # Swap and heapify if the largest is not the current node
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

Core Operation 2: Build Max Heap¶

Build a max-heap by starting from the last non-leaf node and moving upwards to ensure the entire array satisfies the max-heap property. The last non-leaf node has index n // 2 - 1 (where n is the array length).

def build_max_heap(arr):
    n = len(arr)
    # Start from the last non-leaf node and move up
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

Heap Sort Main Function¶

Heap sort works by:
1. Building a max-heap from the input array.
2. Repeatedly swapping the root (max element) with the last element, then heapifying the remaining elements to maintain the max-heap property.

def heap_sort(arr):
    n = len(arr)
    build_max_heap(arr)  # Construct the max-heap

    # Extract elements one by one and adjust the heap
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # Swap root with current end
        heapify(arr, i, 0)  # Heapify the reduced heap
    return arr

Example Demonstration¶

Using the array [12, 11, 13, 5, 6, 7]:
1. Build Max Heap:
Start from the last non-leaf node (index 2, value 13). After adjusting all nodes, the max-heap becomes [13, 12, 11, 5, 6, 7].

2. Extract Max Elements and Adjust:
   - Swap root (13) with the last element (7), array becomes [7, 12, 11, 5, 6, 13]. Heapify the remaining elements to get [12, 7, 11, 5, 6, 13].
   - Repeat until the array is sorted: [5, 6, 7, 11, 12, 13].

Summary¶

Heap sort efficiently sorts data by leveraging max-heap construction and heapify operations. Key steps include building a max-heap, extracting the maximum element iteratively, and maintaining heap properties. It is an in-place algorithm with O(1) space complexity and O(n log n) time complexity, making it suitable for large datasets.