From cbb64e8ab441750535ced849154f16df4add8d78 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sat, 16 Feb 2019 20:24:03 -0600
Subject: Build heap done!

1. Modifying code so it's easy to test is always worth it!
Easier to identify the next concrete steps and carry them out!
2. Hand build a few arrays helped my understanding.
---
 src/main/BuildHeap.java     | 125 ++++++++++++++++++++++++++++++++++++++++++++
 src/main/NetworkPacket.java |   1 -
 src/test/BuildHeapTest.java |  28 ++++++++++
 3 files changed, 153 insertions(+), 1 deletion(-)
 create mode 100644 src/main/BuildHeap.java
 create mode 100644 src/test/BuildHeapTest.java

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
-- 
cgit v1.2.3