堆排序动态演示 (树形结构)

请在上方输入数字构建树，或点击“随机生成”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
def heapify(arr, n, i):
    """
    这个函数用于维护最大堆的性质。
    
    参数:
    arr -- 目标数组
    n   -- 堆的大小
    i   -- 根节点的索引
    """
    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):
    """
    堆排序的主函数
    """
    n = len(arr)

    # --- 第一阶段: 构建最大堆 ---
    # 从最后一个非叶子节点开始，向上遍历到根节点
    # 最后一个非叶子节点的索引是 n // 2 - 1
    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]
        
        # 交换后，堆的大小减 1，并在缩小的堆上重新调用 heapify 调整根节点
        # 注意此时 n 的值变为 i，代表堆的有效大小
        heapify(arr, i, 0)
    
    return arr

# --- 示例 ---
if __name__ == "__main__":
    # 从你之前的动画中取一个默认示例
    sample_array = [50, 16, 48, 8, 12, 35, 21]
    
    print("原始数组:", sample_array)
    
    sorted_array = heap_sort(sample_array.copy()) # 传入一个副本以保留原数组
    
    print("排序后的数组:", sorted_array)

    # 另一个示例
    another_array = [10, 80, 30, 90, 40, 50, 70]
    print("\n原始数组:", another_array)
    sorted_array = heap_sort(another_array.copy())
    print("排序后的数组:", sorted_array)