问题 4.3。构建堆
时限:1秒
内存限制:256 MB
构建堆是堆排序算法的关键步骤。该算法在最坏情况下的运行时间为 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实现这个问题
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- togolife 2021-12-13 23:01关注
n = int(input()) a = list(map(int,input().split())) exchs = [] pos = n // 2 - 1 while pos >= 0: i = pos while 2 * i + 1 < n: left = 2 * i + 1 right = left + 1 if a[i] < a[left] and (right >= n or a[i] < a[right]): break t = left if right < n and a[right] < a[left]: t = right if a[i] > a[t]: a[i],a[t] = a[t],a[i] exchs.append([i, t]) i = t pos -= 1 print (len(exchs)) for exch in exchs: print (exch[0], exch[1])
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 1无用
悬赏问题
- ¥15 HFSS 中的 H 场图与 MATLAB 中绘制的 B1 场 部分对应不上
- ¥15 如何在scanpy上做差异基因和通路富集?
- ¥20 关于#硬件工程#的问题,请各位专家解答!
- ¥15 关于#matlab#的问题:期望的系统闭环传递函数为G(s)=wn^2/s^2+2¢wn+wn^2阻尼系数¢=0.707,使系统具有较小的超调量
- ¥15 FLUENT如何实现在堆积颗粒的上表面加载高斯热源
- ¥30 截图中的mathematics程序转换成matlab
- ¥15 动力学代码报错,维度不匹配
- ¥15 Power query添加列问题
- ¥50 Kubernetes&Fission&Eleasticsearch
- ¥15 報錯:Person is not mapped,如何解決?