Given an unsorted stream of integers, we need to find the medians at the scanned numbers. For a given data we need to sort the data and need to find the median. Once the median is calculated we get the data and need to resort the data to find the data. Basically we need to find a data structure where we need to store our data sorted after every insertion in efficient way.
Possible Solutions.
Solution A:
1. store the unsorted data in array
2. use median of medians to find the median.
Overall time complexity is quadratic.
insertion O(1)
median find O(N) at each iteration.
Solution B:
Keep the data sorted after every iteration. Once we get the data insert the data at sorted position. This requires shifting of the element. So after every insert we need O(N) time to shift the data but median find will take O(1) now.
Solution C:
Sorted Link List:
1. insertion O(1)
2. find median O(N)
Solution D:
Balanced Binary Search Tree:
1. Insertion O(log N).
2. Median Find O(1)
Solution E:
Let us try better and simple approach. We can use two heaps simultaneously, a max heap and min heap with two requirements. First condition the max heap contains smallest part of the half of numbers and min heap contains largest part of half of numbers. So number is max heap are always less than equal to min heap. Second condition is that number of elements in in max heap is greater than equal to min heap (in case of N is even both have same numbers. In case N is odd then max heap has N/2 + 1 numbers but min heap has N /2 numbers).
If heap is created and N is even then median = average of root elements of two heaps.
If N is odd then median = root of max heap.
So the above approach will have two methods.
one to insert element in heap.
Another to find the median. The first method takes care of two conditions listed above.
Insertion steps:
1. we take two different steps for data insertion based on the total current size. In both the cases we need to add data in max heap only.
let us take even case.
In case of even after addition of data in max heap our size criteria will remain satisfied.
In case of odd numbers then if we add data into max heap then size of max heap = N+2 and size of min heap = N. in this case we need to move one elements from max heap to min heap.
In case total no of elements = 2N. We insert element into the max heap. If the inserted element is less than root element in min heap. We need to just insert element into max heap and we are done.
if element is greater than the min element in the min heap. Need to exchange the root of the max heap and root of min heap. then heapify and insert elements into the max heap.
https://gist.github.com/Vedrana/3675434
Possible Solutions.
Solution A:
1. store the unsorted data in array
2. use median of medians to find the median.
Overall time complexity is quadratic.
insertion O(1)
median find O(N) at each iteration.
Solution B:
Keep the data sorted after every iteration. Once we get the data insert the data at sorted position. This requires shifting of the element. So after every insert we need O(N) time to shift the data but median find will take O(1) now.
Solution C:
Sorted Link List:
1. insertion O(1)
2. find median O(N)
Solution D:
Balanced Binary Search Tree:
1. Insertion O(log N).
2. Median Find O(1)
Solution E:
Let us try better and simple approach. We can use two heaps simultaneously, a max heap and min heap with two requirements. First condition the max heap contains smallest part of the half of numbers and min heap contains largest part of half of numbers. So number is max heap are always less than equal to min heap. Second condition is that number of elements in in max heap is greater than equal to min heap (in case of N is even both have same numbers. In case N is odd then max heap has N/2 + 1 numbers but min heap has N /2 numbers).
If heap is created and N is even then median = average of root elements of two heaps.
If N is odd then median = root of max heap.
So the above approach will have two methods.
one to insert element in heap.
Another to find the median. The first method takes care of two conditions listed above.
Insertion steps:
1. we take two different steps for data insertion based on the total current size. In both the cases we need to add data in max heap only.
let us take even case.
In case of even after addition of data in max heap our size criteria will remain satisfied.
In case of odd numbers then if we add data into max heap then size of max heap = N+2 and size of min heap = N. in this case we need to move one elements from max heap to min heap.
In case total no of elements = 2N. We insert element into the max heap. If the inserted element is less than root element in min heap. We need to just insert element into max heap and we are done.
if element is greater than the min element in the min heap. Need to exchange the root of the max heap and root of min heap. then heapify and insert elements into the max heap.
https://gist.github.com/Vedrana/3675434
No comments:
Post a Comment