堆排序（python）

解题思路:

注意事项:

参考代码:

def heapify(nums, n, i):

    if len(nums) <= 1:

        return nums

    largest = i  # 初始化最大值为当前节点

    left = 2 * i + 1  # 左子节点的索引

    right = 2 * i + 2  # 右子节点的索引

    # 如果左子节点存在且大于当前节点，则更新最大值

    if left < n and nums[left] > nums[largest]:

        largest = left

    # 如果右子节点存在且大于当前节点，则更新最大值

    if right < n and nums[right] > nums[largest]:

        largest = right

    # 如果最大值不是当前节点，则交换它们的位置，并递归调整子树

    if largest != i:

        nums[i], nums[largest] = nums[largest], nums[i]

        heapify(nums, n, largest)

def heap_sort(nums):

    n = len(nums)

    # 构建最大堆

    for i in range(n // 2 - 1, -1, -1):

        heapify(nums, n, i)

    # 逐步取出最大值并进行排序

    for i in range(n - 1, 0, -1):

        nums[0], nums[i] = nums[i], nums[0]  # 将最大值与最后一个元素交换

        heapify(nums, i, 0)  # 调整新的根节点

    return nums

n = int(input())

nums = list(map(int, input().split()))

result = heap_sort(nums)

print(' '.join(map(str, result)))