用Python，计算输入特定数列之后，输出构建最小堆需要交换的两个数和交换的次数

Question

问题遇到的现象和发生背景

构建堆是堆排序算法的关键步骤。该算法在最坏情况下的运行时间为 O(n log n)将数组转化为堆，需要对其元素进行多次交换。我们将交换称为交换元素 A[i] 和 A[j] 的基本操作。你在这个任务中的目标是将一个给定的数组转换成一个线性数量的交换的堆
######数据输入输出例子解释
输入第一行包含数字 n。下一行指定了一个数字数组 A[0], …… , A[n − 1] (1< n< 10^5; 0< A[i]< 10^9 for all 0< i< n - 1 ;所有A[i]都是成对不同的；i≠qj).输出输出的第一行必须包含交换次数m，必须满足不等式0 < m < 4 n。以下 m 行中的每一行都应指定数组 A 的两个元素的交换。每个交换由一对不同的索引 0< i≠qj< n - 1 定义，其中一个等式 j = 2i + 1, j = 2i + 2, i = 2j + 1 or i = 2j + 2 都满足了。按照指定的顺序应用所有的交换后，数组应该变成一个最小堆，即所有的都必须满足以下两个条件0< i< n -1
如果 2i + 1< n − 1，则 A[i] < A[2i + 1]。
如果 2i + 2< n − 1，则 A[i] < A[2i + 2]。

问题相关例子

1.输入
6
0 1 2 3 4 5
输出
0
2.输入
6
7 6 5 4 3 2
输出
4
2 5
1 4
0 2
2 5

我的解答思路和尝试过的方法

我想要达到的结果

用Python，计算输入特定数列之后，输出构建最小堆需要交换的两个数和交换的次数

Answer 1

result_list = []


# 调节子树为小根堆,从1开始为有效位，0是临时作用
def HeapAdjust(item_list: list, k: int, length: int):
    item_list[0] = item_list[k]
    i = k * 2
    while i <= length:
        if i < length and item_list[i] > item_list[i + 1]:  # 找儿子中小的
            i += 1
        if item_list[i] >= item_list[0]:
            break
        else:
            result_list.append(str(k - 1)+' '+str(i - 1))
            item_list[k] = item_list[i]
            k = i
        i *= 2
    item_list[k] = item_list[0]
    return item_list


def BuildMinHeap(item_list: list):
    length = len(item_list) - 1
    for i in range(int(length / 2), 0, -1):
        item_list = HeapAdjust(item_list, i, length)
    return item_list


def HeapSort(item_list: list):
    item_list = BuildMinHeap(item_list)
    """ # 如果要真的堆排序形成大根堆，下面的就不要注释
    length = len(item_list) - 1
    for i in range(length, 1, -1):
        item_list[1], item_list[i] = item_list[i], item_list[1]
        item_list = HeapAdjust(item_list, 1, i - 1)
    """
    return item_list


def main():
    item_list = [0]
    _ = eval(input())
    num_str = input()
    num_str_list = num_str.strip().split()
    num_str_list = [eval(item) for item in num_str_list]
    item_list.extend(num_str_list)
    HeapSort(item_list)
    print(len(result_list))
    for item in result_list:
        print(item)


main()

"""
6
0 1 2 3 4 5
6
7 6 5 4 3 2
"""