1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
# python3
def sift_down(i, data, swaps):
max_index = i
l = 2 * i + 1
if l < len(data) and data[l] < data[max_index]:
max_index = l
r = 2 * i + 2
if r < len(data) and data[r] < data[max_index]:
max_index = r
if i != max_index:
temp = data[i];
swaps.append((i, max_index))
data[i] = data[max_index]
data[max_index] = temp
sift_down(max_index, data, swaps)
def get_swaps(data):
swaps = []
for i in range(int((len(data) - 1) / 2), -1, -1):
sift_down(i, data, swaps)
return swaps
def build_heap(data):
"""Build a heap from ``data`` inplace.
Returns a sequence of swaps performed by the algorithm.
"""
# The following naive implementation just sorts the given sequence
# using selection sort algorithm and saves the resulting sequence
# of swaps. This turns the given array into a heap, but in the worst
# case gives a quadratic number of swaps.
#
swaps = []
for i in range(len(data)):
for j in range(i + 1, len(data)):
if data[i] > data[j]:
swaps.append((i, j))
data[i], data[j] = data[j], data[i]
return swaps
def main():
n = int(input())
data = list(map(int, input().split()))
assert len(data) == n
# swaps = build_heap(data)
swaps = get_swaps(data)
print(len(swaps))
for i, j in swaps:
print(i, j)
if __name__ == "__main__":
main()
|
