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 - 2 files changed, 125 insertions(+), 1 deletion(-) create mode 100644 src/main/BuildHeap.java (limited to 'src/main') 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 getSwaps(int[] data) { + List 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 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 swaps) { + out.println(swaps.size()); + for (Swap swap : swaps) { + out.println(swap.index1 + " " + swap.index2); + } + } + + private List generateSwaps(int[] data) { + List 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 swaps = generateSwaps(data); + List 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; -- cgit v1.2.3