Heap Sort (Python)

[qingquan-li]

heap_size = 0  # global variable


def left(i):
    return 2 * i + 1


def right(i):
    return 2 * i + 2


def max_heapify(arr, i):
    global heap_size  # Access the global heap size
    left_child_index = left(i)
    right_child_index = right(i)
    largest = i

    # Check if the left child exists and is greater than the current node
    if left_child_index < heap_size and arr[left_child_index] > arr[largest]:
        largest = left_child_index

    # Check if the right child exists and is greater than the current largest
    if right_child_index < heap_size and arr[right_child_index] > arr[largest]:
        largest = right_child_index

    # If the largest is not the current node, swap and continue heapifying
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        max_heapify(arr, largest)


def build_max_heap(arr):
    global heap_size
    heap_size = len(arr)  # Set the global heap size for the entire build process
    # Start from the last non-leaf node and go up to the root
    for i in range((heap_size // 2) - 1, -1, -1):
        max_heapify(arr, i)


def HeapSort(arr):
    global heap_size
    build_max_heap(arr)
    # Repeatedly extract the max element and rebuild the heap
    for i in range(len(arr) - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # Swap the root (max element) with the last element
        heap_size -= 1  # Reduce the size of the heap
        max_heapify(arr, 0)  # Restore the heap property


arr = [3, 6, 1, 8, 12, 4, 7]
HeapSort(arr)
print("Sorted array:", arr)  # Sorted array: [1, 3, 4, 6, 7, 8, 12]