问题遇到的现象和发生背景
构建堆是堆排序算法的关键步骤。该算法在最坏情况下的运行时间为 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构建堆,写一下注释