@Test public void testRunningMedian() { int[] elements = { 5, 15, 1, 3, 2, 8, 7 }; int[] expected = { 5, 10, 5, 4, 3, 4, 5 }; int[] actual = runningMedian(elements); Assert.assertArrayEquals(expected, actual); }
public static int[] runningMedian(int[] elements) { final MinHeap<Integer> minHeap = new MinHeap<Integer>(new Integer[] {}); final MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(new Integer[] {}); final int[] medians = new int[elements.length]; int median = 0; int element = 0; boolean isElementLessThanMedian = false; Heap<Integer> heapWhereElementToBeInserted = null; Heap<Integer> otherHeap = null; for (int i = 0; i < elements.length; ++i) { element = elements[i]; isElementLessThanMedian = element < median; heapWhereElementToBeInserted = heapWhereElementToBeInserted(isElementLessThanMedian, minHeap, maxHeap); otherHeap = heapWhereElementToBeInserted == minHeap ? maxHeap : minHeap; transferTopItemIfRequired(heapWhereElementToBeInserted, otherHeap); heapWhereElementToBeInserted.insert(element); if (isTheSizeOfBothHeapsEqual(minHeap, maxHeap)) { median = average(minHeap.root(), maxHeap.root()); } else { median = heapWhereElementToBeInserted.root(); } medians[i] = median; } return medians; }
PracticeQuestionsCh10 { public static int[] runningMedian(int[] elements) { final MinHeap<Integer> minHeap = new MinHeap<Integer>(new Integer[] {}); final MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(new Integer[] {}); final int[] medians = new int[elements.length]; int median = 0; int element = 0; boolean isElementLessThanMedian = false; Heap<Integer> heapWhereElementToBeInserted = null; Heap<Integer> otherHeap = null; for (int i = 0; i < elements.length; ++i) { element = elements[i]; isElementLessThanMedian = element < median; heapWhereElementToBeInserted = heapWhereElementToBeInserted(isElementLessThanMedian, minHeap, maxHeap); otherHeap = heapWhereElementToBeInserted == minHeap ? maxHeap : minHeap; transferTopItemIfRequired(heapWhereElementToBeInserted, otherHeap); heapWhereElementToBeInserted.insert(element); if (isTheSizeOfBothHeapsEqual(minHeap, maxHeap)) { median = average(minHeap.root(), maxHeap.root()); } else { median = heapWhereElementToBeInserted.root(); } medians[i] = median; } return medians; } }
PracticeQuestionsCh10 { public static int[] runningMedian(int[] elements) { final MinHeap<Integer> minHeap = new MinHeap<Integer>(new Integer[] {}); final MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(new Integer[] {}); final int[] medians = new int[elements.length]; int median = 0; int element = 0; boolean isElementLessThanMedian = false; Heap<Integer> heapWhereElementToBeInserted = null; Heap<Integer> otherHeap = null; for (int i = 0; i < elements.length; ++i) { element = elements[i]; isElementLessThanMedian = element < median; heapWhereElementToBeInserted = heapWhereElementToBeInserted(isElementLessThanMedian, minHeap, maxHeap); otherHeap = heapWhereElementToBeInserted == minHeap ? maxHeap : minHeap; transferTopItemIfRequired(heapWhereElementToBeInserted, otherHeap); heapWhereElementToBeInserted.insert(element); if (isTheSizeOfBothHeapsEqual(minHeap, maxHeap)) { median = average(minHeap.root(), maxHeap.root()); } else { median = heapWhereElementToBeInserted.root(); } medians[i] = median; } return medians; }  }
PracticeQuestionsCh10 { public static int[] runningMedian(int[] elements) { final MinHeap<Integer> minHeap = new MinHeap<Integer>(new Integer[] {}); final MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(new Integer[] {}); final int[] medians = new int[elements.length]; int median = 0; int element = 0; boolean isElementLessThanMedian = false; Heap<Integer> heapWhereElementToBeInserted = null; Heap<Integer> otherHeap = null; for (int i = 0; i < elements.length; ++i) { element = elements[i]; isElementLessThanMedian = element < median; heapWhereElementToBeInserted = heapWhereElementToBeInserted(isElementLessThanMedian, minHeap, maxHeap); otherHeap = heapWhereElementToBeInserted == minHeap ? maxHeap : minHeap; transferTopItemIfRequired(heapWhereElementToBeInserted, otherHeap); heapWhereElementToBeInserted.insert(element); if (isTheSizeOfBothHeapsEqual(minHeap, maxHeap)) { median = average(minHeap.root(), maxHeap.root()); } else { median = heapWhereElementToBeInserted.root(); } medians[i] = median; } return medians; }  static int[] kSort(Integer[] arr, int k); static int[] runningMedian(int[] elements); }
PracticeQuestionsCh10 { public static int[] runningMedian(int[] elements) { final MinHeap<Integer> minHeap = new MinHeap<Integer>(new Integer[] {}); final MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(new Integer[] {}); final int[] medians = new int[elements.length]; int median = 0; int element = 0; boolean isElementLessThanMedian = false; Heap<Integer> heapWhereElementToBeInserted = null; Heap<Integer> otherHeap = null; for (int i = 0; i < elements.length; ++i) { element = elements[i]; isElementLessThanMedian = element < median; heapWhereElementToBeInserted = heapWhereElementToBeInserted(isElementLessThanMedian, minHeap, maxHeap); otherHeap = heapWhereElementToBeInserted == minHeap ? maxHeap : minHeap; transferTopItemIfRequired(heapWhereElementToBeInserted, otherHeap); heapWhereElementToBeInserted.insert(element); if (isTheSizeOfBothHeapsEqual(minHeap, maxHeap)) { median = average(minHeap.root(), maxHeap.root()); } else { median = heapWhereElementToBeInserted.root(); } medians[i] = median; } return medians; }  static int[] kSort(Integer[] arr, int k); static int[] runningMedian(int[] elements); static final Logger LOGGER; }