import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {//小顶堆是PriorityQueue的默认结构,所以大顶堆需要重写compare方法,做一个比较器
private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>(){
public int compare(Integer o1, Integer o2){
return o2 - o1;
}
});
int count = 0;
public void Insert(Integer num) {//如果奇数位进大顶堆,偶数位进小顶堆,总数奇数个的所有数字的中位数在minHeap的顶端。反之,在maxHeap的顶端
count++;
if((count & 1) == 0){//先进大顶堆,再把大顶堆中最大的放入小顶堆,则说明大顶堆中最大的数字都小于等于小顶堆中的数字。
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
}else{//反之,先进小顶堆,再把小顶堆的顶部放入大顶堆,说明小顶堆中最小的数字都大于等于大顶堆,保证了小顶堆中所有数字大于大顶堆
minHeap.offer(num);
maxHeap.offer(minHeap.poll());
}
}//并且每个num都经历过一次比较的过程,一直能够保证大顶堆和小顶堆的大小差值不超过1.
//当数字量为奇数,大顶堆的堆顶是小的那count/2的数中最大的,小顶堆的堆顶是大的count/2的数中最小的,则中位数就可以求了
public Double GetMedian() {
if((count & 1) == 0)
return (double)(minHeap.peek() + maxHeap.peek()) / 2.0;
else
return (double)maxHeap.peek();
}
//本方法奇数位进小顶堆,如果count为奇数,最后返回的中位数 应该在maxHeap中
//还可以偶数位进小顶堆,如果count为奇数,最后返回的中位数 应该在minHeap中
//如果count为偶数,则就是求两个堆顶 / 2的值
}
“以上方法使用优先级队列的方式,JDK1.5之后可以扩容。”还没有考证这句话。
Heap底层用的是Vector(ArrayList),固定数组,有扩容负担。
《程序员面试宝典》上写的是先设计一个没有扩容负担的堆结构,然后在那个自己设计的堆结构的基础上做这道题,还需要再看。