Share the joy
Problem: If a random array is [2, 20, 40, 60, 50, 65, 25, 10, 30, 35, 52, 63, 67, 3], find the median of the array.
1. For each new Element in array, if it is less than the root of max heap, put it in the max heap; or put it in the min heap.
2. Adjust 2 heaps, in order that number of element in 2 heaps differ less than 1.
If element numbers in 2 heaps differ more than 1, put the root of the heap which has more element in the heap which has less element. Adjust 2 heaps.
Put all elements into 2 heaps.
If number of elements are the same, the median is (root_of_max_heap + root_of_min_heap) / 2.
If number of elements are not the same, the median is the root of heap which has more element.