题目
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
程序核心思想
核心思想大家应该都是一样的，用堆结构来做。
构造一个大根堆，一个小根堆，数据流中出来一个数，那么如果这个数比大根堆的堆顶还要大，那么这个数进入小根堆的底部，然后heapify调整（跟它的父节点比较，如果比父节点小，那么交换...），如果比大根堆的堆顶小，那么进入大根堆的底部，然后heapify调整（跟它的父节点比较，如果比父节点大，那么交换...）。同时还有记录进入大根堆和小根堆的总数，如果大根堆和小根堆的差大于1的话，那么如果大根堆的总数比小根堆多，那么把大根堆的堆顶放入小根堆，否则把小根堆的堆顶放入大根堆，然后大根堆和小根堆都要heapify，弹出东西的那个堆的heapify是从index=0的位置开始（因为做了一个swap（0，堆底）的操作），放入东西的那个堆的heapify还是跟之前一样，是从堆底到堆顶的。
剩下的就是输出一个数还是两个数的平均数的部分了，比较简单，不说了。
然后我发现，网路上面的解法比我的要简单很多，因为他们使用了一个叫做优先队列的结构。
PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。优先队列的作用是能保证每次取出的元素都是队列中权值最小的，这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator）。
Tips
插入元素：add()、offer()
删除元素：poll()
获取队头元素：peek()
获取队列大小：size()
清空队列：clear()
是否包含某个元素：contains()
清除一个指定元素：remove()
优先队列默认按从小到大的顺序排列，如果需要一个大顶堆的话，需要重写compar方法。
代码
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
PriorityQueue<Integer> pqMax = new PriorityQueue<Integer>(new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2){
return o2 - o1;
}
});
PriorityQueue<Integer> pqMin = new PriorityQueue<Integer>();
public void Insert(Integer num) {
if(pqMax.size() == 0 || num < pqMax.peek()){
pqMax.offer(num);
}else{
pqMin.offer(num);
}
if(Math.abs(pqMax.size() - pqMin.size()) > 1){
if(pqMax.size() > pqMin.size()){
pqMin.offer(pqMax.poll());
}else{
pqMax.offer(pqMin.poll());
}
}
}
public Double GetMedian() {
int count = pqMax.size() + pqMin.size();
if(count % 2 == 1){
if(pqMax.size() > pqMin.size()){
return 1.0 * pqMax.peek();
}else{
return 1.0 * pqMin.peek();
}
}else{
return (pqMax.peek() + pqMin.peek())/2.0;
}
}
}
public class Solution {
int count = 0;
int[] arrMax = new int[10000];
int[] arrMin = new int[10000];
int left = 0;
int right = 0;
public void Insert(Integer num) {
count++;
if(num > arrMax[0]){
//去小根堆
arrMin[right] = num;//需上移
heapifyMin(arrMin, right);
right++;
}else{
//去大根堆
arrMax[left] = num;//需上移
heapifyMax(arrMax, left);
left++;
}
if(Math.abs(right - left) > 1){
if(left > right){
arrMin[right] = arrMax[0];
heapifyMin(arrMin, right++);
swap(arrMax, 0, --left);
heapifyMaxx(arrMax, left-1);
}else{
arrMax[left] = arrMin[0];
heapifyMax(arrMax, left++);
swap(arrMin, 0, --right);
heapifyMinn(arrMin, right-1);
}
}
}
public Double GetMedian() {
if(count % 2 == 1){
if(left > right){
return 1.0 * arrMax[0];
}else{
return 1.0 * arrMin[0];
}
}else{
return (arrMax[0] + arrMin[0])/2.0;
}
}
public void heapifyMax(int[] arr, int end){
int index = end;
int father = (end - 1)/2;
while(father >= 0){
if(arr[father] < arr[index]){
swap(arr, father, index);
index = father;
father = (index - 1)/2;
}else{
break;
}
}
}
public void heapifyMin(int[] arr, int end){
int index = end;
int father = (end - 1)/2;
while(father >= 0){
if(arr[father] > arr[index]){
swap(arr, father, index);
index = father;
father = (index - 1)/2;
}else{
break;
}
}
}
public void heapifyMaxx(int[] arr, int end) {
int index = 0;
int left = 2 * index + 1;
while (left <= end) {
int max = left + 1 <= end && arr[left + 1] > arr[left] ? left + 1: left;
if(arr[max] > arr[index]){
swap(arr, index, max);
index = max;
left = 2 * index + 1;
}else{
break;
}
}
}
public void heapifyMinn(int[] arr, int end){
int index = 0;
int left = 2 * index + 1;
while (left <= end) {
int min = left + 1 <= end && arr[left + 1] < arr[left] ? left + 1: left;
if(arr[min] < arr[index]){
swap(arr, index, min);
index = min;
left = 2 * index + 1;
}else{
break;
}
}
}
public void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
