@Test public void testKSort() { final Integer[] arr = { 3, 1, 7, 4, 10 }; final int[] expected = { 1, 3, 4, 7, 10 }; int[] actual = kSort(arr, 2); Assert.assertArrayEquals(expected, actual); actual = kSort(arr, 4); Assert.assertArrayEquals(expected, actual); }
public static int[] kSort(Integer[] arr, int k) { final int size = Math.min(2 * k, arr.length); MinHeap<Integer> minHeap = new MinHeap<Integer>(Arrays.copyOf(arr, size)); int[] sorted = new int[arr.length]; int i = 0; for (int j = size + i; j < arr.length; ++i, ++j) { sorted[i] = minHeap.delete(); minHeap.insert(arr[j]); } for (; minHeap.size() > 0; ++i) { sorted[i] = minHeap.delete(); } return sorted; }
PracticeQuestionsCh10 { public static int[] kSort(Integer[] arr, int k) { final int size = Math.min(2 * k, arr.length); MinHeap<Integer> minHeap = new MinHeap<Integer>(Arrays.copyOf(arr, size)); int[] sorted = new int[arr.length]; int i = 0; for (int j = size + i; j < arr.length; ++i, ++j) { sorted[i] = minHeap.delete(); minHeap.insert(arr[j]); } for (; minHeap.size() > 0; ++i) { sorted[i] = minHeap.delete(); } return sorted; } }
PracticeQuestionsCh10 { public static int[] kSort(Integer[] arr, int k) { final int size = Math.min(2 * k, arr.length); MinHeap<Integer> minHeap = new MinHeap<Integer>(Arrays.copyOf(arr, size)); int[] sorted = new int[arr.length]; int i = 0; for (int j = size + i; j < arr.length; ++i, ++j) { sorted[i] = minHeap.delete(); minHeap.insert(arr[j]); } for (; minHeap.size() > 0; ++i) { sorted[i] = minHeap.delete(); } return sorted; }  }
PracticeQuestionsCh10 { public static int[] kSort(Integer[] arr, int k) { final int size = Math.min(2 * k, arr.length); MinHeap<Integer> minHeap = new MinHeap<Integer>(Arrays.copyOf(arr, size)); int[] sorted = new int[arr.length]; int i = 0; for (int j = size + i; j < arr.length; ++i, ++j) { sorted[i] = minHeap.delete(); minHeap.insert(arr[j]); } for (; minHeap.size() > 0; ++i) { sorted[i] = minHeap.delete(); } return sorted; }  static int[] kSort(Integer[] arr, int k); static int[] runningMedian(int[] elements); }
PracticeQuestionsCh10 { public static int[] kSort(Integer[] arr, int k) { final int size = Math.min(2 * k, arr.length); MinHeap<Integer> minHeap = new MinHeap<Integer>(Arrays.copyOf(arr, size)); int[] sorted = new int[arr.length]; int i = 0; for (int j = size + i; j < arr.length; ++i, ++j) { sorted[i] = minHeap.delete(); minHeap.insert(arr[j]); } for (; minHeap.size() > 0; ++i) { sorted[i] = minHeap.delete(); } return sorted; }  static int[] kSort(Integer[] arr, int k); static int[] runningMedian(int[] elements); static final Logger LOGGER; }