调用关系：

                       heap_sort
                 /                  |
build_max_heap_by_down_adjust       |
              \                     |
                maxheap_down_adjust              

堆排序python实现：

def heap_sort(array: list[int]) -> None:
    """
    原地堆排序 (大顶堆实现的从小到大排序)
    """

    # egde case
    if len(array) <= 1:
        return

    # 1. 建堆. 建堆有2种思路：down_adjust 和 up_adjust。详见下文说明
    build_max_heap_by_down_adjust(array)
    # build_max_heap_by_up_adjust(array)

    # 2. loop to sort: 将array首尾换位置，最大值到最后，然后再maxheap_down_adjust
    for i in range(len(array) - 1, 0, -1):
        array[i], array[0] = array[0], array[i]
        maxheap_down_adjust(array, 0, i - 1)

    return

def build_max_heap_by_down_adjust(array: list[int]) -> None:
    # 构建大顶堆 by_down_adjust
    # down_adjust从最后一个非叶子结点起（也可以从叶子结点起，但没必要，因为叶子本身已经是合法的堆结构），
    # 倒序地通过maxheap_down_adjust构建每个子大顶堆
    lenth = len(array)
    for i in range(lenth // 2 - 1, -1, -1):
        # i as maxheap root_index
        maxheap_down_adjust(array, i, lenth - 1)

    print(f"heap built as: {array}")
    return

def maxheap_down_adjust(array: list[int], root_index: int, end_index: int) -> None:
    """
    maxheap_down_adjust 以root_index为根的一个大顶堆的向下调整。
    【前提条件是root的左右结点已经是大顶堆根，这样才能做到root只需要关注自己的左右结点】

    :param array: 待排序的数组，可通过下标推断parent node和child node
    :param root_index: 大顶堆根的index
    :param end_index: 推断parent node和child node时，最后一个合法index
    :return: None
    """

    # down_adjust过程：
    # 1. if 树根（array[root_index]）的左子结点存在，且左子结点值 > 树根，将树根与左子结点进行值交换, and build_max_heap(array, left_child_index)
    # 2. if 树根（array[root_index]）的右子结点存在，且右子结点值 > 树根，将树根与右子结点进行值交换, and build_max_heap(array, right_child_index)
    if root_index > end_index:
        raise ValueError(f"err: root_index({root_index}) > end_index({end_index})")

    left_child_index, right_child_index = 2 * root_index + 1, 2 * root_index + 2

    if left_child_index <= end_index:
        left_child_value = array[left_child_index]
        if left_child_value > array[root_index]:
            # swap value of root and left_child
            array[left_child_index], array[root_index] = array[root_index], array[left_child_index]
            # maxheap_down_adjust left_child recursively
            maxheap_down_adjust(array, left_child_index, end_index)

    if right_child_index <= end_index:
        right_child_value = array[right_child_index]
        if right_child_value > array[root_index]:
            # swap value of root and right_child
            array[root_index], array[right_child_index] = array[right_child_index], array[root_index]
            # maxheap_down_adjust right_child recursively
            maxheap_down_adjust(array, right_child_index, end_index)

    return

def build_max_heap_by_up_adjust(array: list[int]) -> None:
    # 构建大顶堆 by_up_adjust
    # up_adjust从首个结点起，
    # 顺序地对每个节点使用maxheap_up_adjust进行堆调整
    lenth = len(array)
    for i in range(lenth):
        maxheap_up_adjust(array, i)
    print(f"heap built as: {array}")
    return

def maxheap_up_adjust(array: list[int], bottom_index: int) -> None:
    child_index = bottom_index
    parent_index = (child_index - 1) // 2

    if parent_index >= 0 and array[child_index] > array[parent_index]:
        # swap parent and child
        array[child_index], array[parent_index] = array[parent_index], array[child_index]
        # 继续以 parent_index 为 bottom 节点进行向上调整
        maxheap_up_adjust(array, parent_index)

test_list = [134, 5, 565, 35, 676, 3, 2, 1, 4, 5]
heap_sort(test_list)
print(test_list)

down_adjust和up_adjust

down_adjust（向下调整）：

down_adjust将调整起点视为堆顶元素，从堆顶开始向下调整堆结构，以维护堆的性质（大顶堆或小顶堆）。这个操作通常在堆顶元素被移除或替换时使用，例如在堆排序算法中，将堆顶元素与最后一个元素交换后，需要通过down_adjust重新调整堆结构。

down_adjust的具体步骤如下：

• 从堆顶元素开始，找到其左右孩子中较大（大顶堆）或较小（小顶堆）的一个；
• 如果当前节点比较大（大顶堆）或较小（小顶堆）的孩子还要大（大顶堆）或小（小顶堆），则不需要调整，结束；
• 否则，将当前节点与较大（大顶堆）或较小（小顶堆）的孩子交换；继续向下调整，直到叶子节点或不需要交换为止。

up_adjust（向上调整）：

up_adjust将调整起点视为堆底元素，从堆底开始向上调整堆结构，以维护堆的性质（大顶堆或小顶堆）。这个操作通常在向堆中插入新元素时使用，例如在构建堆或实现优先级队列时，需要通过up_adjust调整堆结构。

up_adjust的具体步骤如下：

• 从新插入的元素开始，找到其父节点；
• 如果当前节点比其父节点要小（大顶堆）或大（小顶堆），则不需要调整，结束；
• 否则，将当前节点与其父节点交换；继续向上调整，直到根节点或不需要交换为止。