diff options
| -rw-r--r-- | src/main/BuildHeap.java | 125 | ||||
| -rw-r--r-- | src/main/NetworkPacket.java | 1 | ||||
| -rw-r--r-- | src/test/BuildHeapTest.java | 28 |
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 |