blob: d0cccf803c68d617b3f19b3d7d2184b28e3f37b5 (
plain)
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class BuildHeap {
private FastScanner in;
private PrintWriter out;
public static void main(String[] args) throws IOException {
new BuildHeap().solve();
}
static List<Swap> getSwaps(int[] data) {
List<Swap> swaps = new ArrayList<>();
for (int i = (data.length - 1) / 2; i >= 0; i--) {
siftDown(i, data, swaps);
}
return swaps;
}
// Direct implementation from lecture notes, except adjustment for 0 based indexing
private static void siftDown(int i, int[] data, List<Swap> swaps) {
int maxIndex = i;
int l = 2 * i + 1;
if (l < data.length && data[l] < data[maxIndex])
maxIndex = l;
int r = 2 * i + 2;
if (r < data.length && data[r] < data[maxIndex])
maxIndex = r;
if (i != maxIndex) {
int temp = data[i];
swaps.add(new Swap(i, maxIndex));
data[i] = data[maxIndex];
data[maxIndex] = temp;
siftDown(maxIndex, data, swaps);
}
}
private int[] readData() throws IOException {
int[] data;
int n = in.nextInt();
data = new int[n];
for (int i = 0; i < n; ++i) {
data[i] = in.nextInt();
}
return data;
}
private void writeResponse(List<Swap> swaps) {
out.println(swaps.size());
for (Swap swap : swaps) {
out.println(swap.index1 + " " + swap.index2);
}
}
private List<Swap> generateSwaps(int[] data) {
List<Swap> swaps = new ArrayList<>();
// 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.
//
// This is the naive implementation. getSwaps is more efficient!
for (int i = 0; i < data.length; ++i) {
for (int j = i + 1; j < data.length; ++j) {
if (data[i] > data[j]) {
swaps.add(new Swap(i, j));
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
}
return swaps;
}
private void solve() throws IOException {
in = new FastScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
int[] data = readData();
// List<Swap> swaps = generateSwaps(data);
List<Swap> swaps = getSwaps(data);
writeResponse(swaps);
out.close();
}
static class Swap {
int index1;
int index2;
Swap(int index1, int index2) {
this.index1 = index1;
this.index2 = index2;
}
}
static class FastScanner {
private BufferedReader reader;
private StringTokenizer tokenizer;
FastScanner() {
reader = new BufferedReader(new InputStreamReader(System.in));
tokenizer = null;
}
String next() throws IOException {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
}
|
