heap sort that uses a max heap to sort an array in ascending order complexity on logn max heapify helper for maxheapsort iterate from last parent to first iterate from currentparent to lastparent find greatest child of currentparent swap if child is greater than parent if no swap occurred no need to keep iterating heap sort that uses a min heap to sort an array in ascending order complexity on logn min heapify helper for minheapsort offset lastparent by the start lastparent calculated as if start index was 0 all array accesses need to be offset by start iterate from last parent to first iterate from currentparent to lastparent find lesser child of currentparent swap if child is less than parent if no swap occurred no need to keep iterating heap sort that uses a max heap to sort an array in ascending order complexity o n log n max heapify helper for max_heap_sort iterate from last parent to first iterate from current_parent to last_parent find greatest child of current_parent swap if child is greater than parent if no swap occurred no need to keep iterating heap sort that uses a min heap to sort an array in ascending order complexity o n log n min heapify helper for min_heap_sort offset last_parent by the start last_parent calculated as if start index was 0 all array accesses need to be offset by start iterate from last parent to first iterate from current_parent to last_parent find lesser child of current_parent swap if child is less than parent if no swap occurred no need to keep iterating
def max_heap_sort(arr, simulation=False):
    
    iteration = 0
    if simulation:
        print("iteration",iteration,":",*arr)
        
    for i in range(len(arr) - 1, 0, -1):
        iteration = max_heapify(arr, i, simulation, iteration)

    if simulation:
                iteration = iteration + 1
                print("iteration",iteration,":",*arr)
    return arr


def max_heapify(arr, end, simulation, iteration):
    
    last_parent = (end - 1) // 2

    
    for parent in range(last_parent, -1, -1):
        current_parent = parent

        
        while current_parent <= last_parent:
            
            child = 2 * current_parent + 1
            if child + 1 <= end and arr[child] < arr[child + 1]:
                child = child + 1

            
            if arr[child] > arr[current_parent]:
                arr[current_parent], arr[child] = arr[child], arr[current_parent]
                current_parent = child
                if simulation:
                    iteration = iteration + 1
                    print("iteration",iteration,":",*arr)
            
            else:
                break
    arr[0], arr[end] = arr[end], arr[0]
    return iteration

def min_heap_sort(arr, simulation=False):
    
    iteration = 0
    if simulation:
        print("iteration",iteration,":",*arr)
        
    for i in range(0, len(arr) - 1):
        iteration = min_heapify(arr, i, simulation, iteration)

    return arr


def min_heapify(arr, start, simulation, iteration):
    
    
    
    end = len(arr) - 1
    last_parent = (end - start - 1) // 2

    
    for parent in range(last_parent, -1, -1):
        current_parent = parent

        
        while current_parent <= last_parent:
            
            child = 2 * current_parent + 1
            if child + 1 <= end - start and arr[child + start] > arr[
                child + 1 + start]:
                child = child + 1
            
            
            if arr[child + start] < arr[current_parent + start]:
                arr[current_parent + start], arr[child + start] = \
                    arr[child + start], arr[current_parent + start]
                current_parent = child
                if simulation:
                    iteration = iteration + 1
                    print("iteration",iteration,":",*arr)
            
            else:
                break
    return iteration