Continuous Median
Category: Heaps
```
Problem Statement
Continuous Median Write a ContinuousMedianHandler class that supports: - The continuous insertion of numbers with the insert method. - The instant (O(1) time) retrieval of the median of the numbers that have been inserted thus far with the getMedian method. The getMedian method has already been written for you. You simply have to write the insert method. Sample Usage // All operations below are performed sequentially. ContinuousMedianHandler(): - // instantiate a ContinuousMedianHandler insert(5): - insert(10): - getMedian(): 7.5 insert(100): - getMedian(): 10 Hints Hint 1 The median of a set of numbers is often, by denition, one of the numbers in the set. Thus, you likely have to store all of the inserted numbers somewhere to be able to continuously compute their median. Hint 2 The median of a set of numbers is either the middle number of that set (if the set has an odd amount of numbers) or the average of the middle numbers (if the set has an even amount of numbers). This means that if you could somehow keep track of the middle number(s) of the set of inserted numbers, you could easily compute the median by nding the indices of the middle numbers and doing some simple calculations. Perhaps storing all of the numbers in a sorted array could work, but what would be the runtime implication of inserting each new number into a sorted array? Hint 3 Realizing that you only need to keep track of the middle numbers in the set of inserted numbers to compute the median, try keeping track of two subsets of the numbers: a max-heap of the lower half of the numbers and a min-heap of the greater half of the numbers. Any time you insert a number, pick the heap to place it in by comparing it to the max / min values of the heaps. Then, re-balance the heaps in an eort to keep their sizes apart by at most one. Doing so will allow you to access the middle number(s) of the set of inserted numbers very easily, which will make calculating the median a trivial computation. Re-balancing the heaps can be accomplished by simply removing a value from the larger heap and inserting it in the smaller one. What are the runtime implications of all these operations? Optimal Space & Time Complexity Insert: O(log(n)) time | O(n) space - where n is the number of inserted numbers
```
Approach & Solution
Solution 1
```
}
} else {
idxToSwap = childOneIdx;
}
if (comparisonFunc.apply(heap.get(idxToSwap), heap.get(currentIdx))) {
swap(currentIdx, idxToSwap, heap);
currentIdx = idxToSwap;
childOneIdx = currentIdx * 2 + 1;
} else {
return;
}
}
}
public void siftUp(int currentIdx, List
Solution 2
```
53 comparisonFunc func;
54 length = heap.size();
55 }
56
57 public List
Solution 3
```java
import java.util.*;
import java.util.function.BiFunction;
class Program {
static class ContinuousMedianHandler {
Heap lowers = new Heap(Program::MAX_HEAP_FUNC, new ArrayList
```
Test Cases
``` Test Case 1 { "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [10], "method": "insert"}, {"arguments": [], "method": "getMedian"}, {"arguments": [100], "method": "insert"}, {"arguments": [], "method": "getMedian"} ] } Test Case 2 { "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [], "method": "getMedian"}, {"arguments": [10], "method": "insert"}, {"arguments": [], "method": "getMedian"} ] } Test Case 3 { "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [10], "method": "insert"}, {"arguments": [100], "method": "insert"}, {"arguments": [], "method": "getMedian"}, {"arguments": [200], "method": "insert"}, {"arguments": [], "method": "getMedian"} ] } Test Case 4 { "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [10], "method": "insert"}, {"arguments": [100], "method": "insert"}, {"arguments": [200], "method": "insert"}, {"arguments": [6], "method": "insert"}, {"arguments": [], "method": "getMedian"}, {"arguments": [13], "method": "insert"}, {"arguments": [], "method": "getMedian"} ] } Test Case 5 { "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [10], "method": "insert"}, {"arguments": [100], "method": "insert"}, {"arguments": [200], "method": "insert"}, {"arguments": [6], "method": "insert"}, {"arguments": [13], "method": "insert"}, {"arguments": [14], "method": "insert"}, {"arguments": [], "method": "getMedian"}, {"arguments": [50], "method": "insert"}, {"arguments": [], "method": "getMedian"} ] } Test Case 6 { "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [10], "method": "insert"}, {"arguments": [100], "method": "insert"}, {"arguments": [200], "method": "insert"}, {"arguments": [6], "method": "insert"}, {"arguments": [13], "method": "insert"}, {"arguments": [14], "method": "insert"}, {"arguments": [50], "method": "insert"}, {"arguments": [51], "method": "insert"}, {"arguments": [], "method": "getMedian"}, {"arguments": [52], "method": "insert"}, {"arguments": [], "method": "getMedian"} ] } Test Case 7 { "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [10], "method": "insert"}, {"arguments": [100], "method": "insert"}, {"arguments": [200], "method": "insert"}, {"arguments": [6], "method": "insert"}, {"arguments": [13], "method": "insert"}, {"arguments": [14], "method": "insert"}, {"arguments": [50], "method": "insert"}, {"arguments": [51], "method": "insert"}, {"arguments": [52], "method": "insert"}, {"arguments": [1000], "method": "insert"}, {"arguments": [], "method": "getMedian"}, {"arguments": [10000], "method": "insert"}, {"arguments": [], "method": "getMedian"} ] } Test Case 8 { "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [10], "method": "insert"}, {"arguments": [100], "method": "insert"}, {"arguments": [200], "method": "insert"}, {"arguments": [6], "method": "insert"}, {"arguments": [13], "method": "insert"}, {"arguments": [14], "method": "insert"}, {"arguments": [50], "method": "insert"}, {"arguments": [51], "method": "insert"}, {"arguments": [52], "method": "insert"}, {"arguments": [1000], "method": "insert"}, {"arguments": [10000], "method": "insert"}, {"arguments": [10001], "method": "insert"}, {"arguments": [], "method": "getMedian"}, {"arguments": [10002], "method": "insert"}, {"arguments": [], "method": "getMedian"} ] } Test Case 9 { "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [10], "method": "insert"}, {"arguments": [100], "method": "insert"}, {"arguments": [200], "method": "insert"}, {"arguments": [6], "method": "insert"}, {"arguments": [13], "method": "insert"}, {"arguments": [14], "method": "insert"}, {"arguments": [50], "method": "insert"}, {"arguments": [51], "method": "insert"}, {"arguments": [52], "method": "insert"}, {"arguments": [1000], "method": "insert"}, {"arguments": [10000], "method": "insert"}, {"arguments": [10001], "method": "insert"}, {"arguments": [10002], "method": "insert"}, {"arguments": [10003], "method": "insert"}, {"arguments": [], "method": "getMedian"}, {"arguments": [10004], "method": "insert"}, {"arguments": [], "method": "getMedian"} ] } Test Case 10 { "classMethodsToCall": [ {"arguments": [5], "method": "insert"}, {"arguments": [10], "method": "insert"}, {"arguments": [100], "method": "insert"}, {"arguments": [200], "method": "insert"}, {"arguments": [6], "method": "insert"}, {"arguments": [13], "method": "insert"}, {"arguments": [14], "method": "insert"}, {"arguments": [50], "method": "insert"}, {"arguments": [51], "method": "insert"}, {"arguments": [52], "method": "insert"}, {"arguments": [1000], "method": "insert"}, {"arguments": [10000], "method": "insert"}, {"arguments": [10001], "method": "insert"}, {"arguments": [10002], "method": "insert"}, {"arguments": [10003], "method": "insert"}, {"arguments": [10004], "method": "insert"}, {"arguments": [75], "method": "insert"}, {"arguments": [], "method": "getMedian"}, {"arguments": [80], "method": "insert"}, {"arguments": [], "method": "getMedian"} ] }