守望_sy
2021-12-12 22:26
采纳率: 63.2%
浏览 84
已结题

怎么用python实现这个问题

问题 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

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

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 无用
    打赏 举报

相关推荐 更多相似问题