043. 编写一个函数，实现堆排序算法

堆排序是一种基于二叉堆的比较排序算法。它利用了堆的性质来高效地排序数组。堆排序分为两个主要步骤：

构建最大堆：将数组转换为一个最大堆。
排序：逐步从堆中取出最大元素，将其放到数组的末尾，并调整堆以保持最大堆的性质。

示例代码

def heapify(arr, n, i):
    """
    堆调整函数，用于维护最大堆的性质。

    参数:
        arr (list): 输入数组。
        n (int): 数组的大小。
        i (int): 当前需要调整的节点索引。
    """
    largest = i  # 初始化最大值为当前节点
    left = 2 * i + 1  # 左子节点
    right = 2 * i + 2  # 右子节点

    # 如果左子节点存在且大于当前最大值
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 如果右子节点存在且大于当前最大值
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值不是当前节点，交换它们并继续调整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    """
    堆排序函数。

    参数:
        arr (list): 输入数组。
    """
    n = len(arr)

    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 逐个从堆中取出最大元素并放到数组末尾
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换堆顶和最后一个元素
        heapify(arr, i, 0)  # 调整剩余的堆

# 测试代码
arr = [12, 11, 13, 5, 6, 7]
print("原始数组：", arr)
heap_sort(arr)
print("排序后的数组：", arr)

运行结果

运行上述代码后，输出如下：

原始数组： [12, 11, 13, 5, 6, 7]
排序后的数组： [5, 6, 7, 11, 12, 13]

代码解释

heapify 函数：

用于维护最大堆的性质。
参数 arr 是输入数组，n 是数组的大小，i 是当前需要调整的节点索引。
通过比较当前节点、左子节点和右子节点，找到最大值的索引 largest。
如果最大值不是当前节点，交换它们，并递归调整子树。

heap_sort 函数：

参数 arr 是输入数组。
首先，通过从最后一个非叶子节点开始向上调整，构建最大堆。
然后，从数组末尾开始，逐步将堆顶元素（最大值）放到数组末尾，并调整剩余的堆。

注意事项

构建最大堆：从最后一个非叶子节点开始向上调整，确保每个子树都满足最大堆的性质。
排序过程：每次将堆顶元素（最大值）放到数组末尾，然后调整剩余的堆，直到整个数组排序完成。
时间复杂度：堆排序的时间复杂度为 O(nlogn)，其中 n 是数组的长度。
空间复杂度：堆排序是原地排序算法，空间复杂度为 O(1)。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)