问题 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 c语言怎么用printf(“\b \b”)与getch()实现黑框里写入与删除?
- ¥20 怎么用dlib库的算法识别小麦病虫害
- ¥15 华为ensp模拟器中S5700交换机在配置过程中老是反复重启
- ¥15 java写代码遇到问题,求帮助
- ¥15 uniapp uview http 如何实现统一的请求异常信息提示?
- ¥15 有了解d3和topogram.js库的吗?有偿请教
- ¥100 任意维数的K均值聚类
- ¥15 stamps做sbas-insar,时序沉降图怎么画
- ¥15 买了个传感器,根据商家发的代码和步骤使用但是代码报错了不会改,有没有人可以看看
- ¥15 关于#Java#的问题,如何解决?