调用关系：
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的具体步骤如下：
- 从新插入的元素开始，找到其父节点；
- 如果当前节点比其父节点要小（大顶堆）或大（小顶堆），则不需要调整，结束；
- 否则，将当前节点与其父节点交换；继续向上调整，直到根节点或不需要交换为止。
