summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorHaidong Ji2019-02-16 20:24:03 -0600
committerHaidong Ji2019-02-16 20:24:03 -0600
commitcbb64e8ab441750535ced849154f16df4add8d78 (patch)
treebf312fe915c698ab6f2d5e41bbc75358553890f9 /src
parent83292a326000d1c7c5695f6cb8b8575081221cda (diff)
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.
Diffstat (limited to 'src')
-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