summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/main/BuildHeap.java125
-rw-r--r--src/main/NetworkPacket.java1
-rw-r--r--src/test/BuildHeapTest.java28
3 files changed, 153 insertions, 1 deletions
diff --git a/src/main/BuildHeap.java b/src/main/BuildHeap.java
new file mode 100644
index 0000000..d0cccf8
--- /dev/null
+++ b/src/main/BuildHeap.java
@@ -0,0 +1,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());
+ }
+ }
+}
+
diff --git a/src/main/NetworkPacket.java b/src/main/NetworkPacket.java
index 7aeea88..4b83129 100644
--- a/src/main/NetworkPacket.java
+++ b/src/main/NetworkPacket.java
@@ -1,4 +1,3 @@
-import java.io.IOException;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
diff --git a/src/test/BuildHeapTest.java b/src/test/BuildHeapTest.java
new file mode 100644
index 0000000..59b1711
--- /dev/null
+++ b/src/test/BuildHeapTest.java
@@ -0,0 +1,28 @@
+import org.junit.jupiter.api.Test;
+
+import java.util.List;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class BuildHeapTest {
+ @Test
+ void test1() {
+ int[] data = {5, 4, 3, 2, 1};
+ List<BuildHeap.Swap> swaps = BuildHeap.getSwaps(data);
+ assertEquals(3, swaps.size());
+ assertEquals(1, swaps.get(0).index1);
+ assertEquals(4, swaps.get(0).index2);
+ assertEquals(0, swaps.get(1).index1);
+ assertEquals(1, swaps.get(1).index2);
+ assertEquals(1, swaps.get(2).index1);
+ assertEquals(3, swaps.get(2).index2);
+ }
+
+ @Test
+ void test2() {
+ int[] data = {1, 2, 3, 4, 5};
+ List<BuildHeap.Swap> swaps = BuildHeap.getSwaps(data);
+ assertEquals(0, swaps.size());
+ }
+
+} \ No newline at end of file