Heap 相关

本文主要是介绍Heap 相关，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

• For example, for arr = [2,3,4], the median is 3.
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Constraints:

• -105 <= num <= 105
• There will be at least one element in the data structure before calling findMedian.
• At most 5 * 104 calls will be made to addNum and findMedian. 

解法： 一个大顶堆（存前半段元素），一个小顶堆（存后半段元素），那么取中位数只需要从堆顶取即可

时间复杂度：

Follow up:

• If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?  

解法：可以直接开个int[100]数组，插入元素进行count[i]++, 查找的时候根据count找到最终的中位数 ，插入和查找 都为O(1) 

• If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

解法：可以把数据分3段：  x < 0 (使用maxheap), x in 0 ~ 100 （使用数组count）, x > 100  （使用minheap）

class MedianFinder {
    private PriorityQueue<Integer> minHeap;
    private PriorityQueue<Integer> maxHeap;
    
    public MedianFinder() {
        minHeap = new PriorityQueue<Integer>((x,y)->x-y);//小顶堆，存后半段
        maxHeap = new PriorityQueue<Integer>((x,y)->y-x);//大顶堆，存前半段
    }
    
    public void addNum(int num) {//O(logN)
        if(maxHeap.isEmpty() || maxHeap.peek()>num) maxHeap.offer(num);//如果小于大顶堆top，放前半段
        else minHeap.offer(num);//否则放后半段
        //保持两堆数量平衡，或者大顶堆多一个
        while(minHeap.size()>maxHeap.size()) maxHeap.offer(minHeap.poll());
        while(minHeap.size()<maxHeap.size()-1) minHeap.offer(maxHeap.poll());
    }
    
    public double findMedian() {//O(1)
        //如果数量一样，去各自头取平均
        if(minHeap.size()==maxHeap.size()) return ((double)minHeap.peek()+(double)maxHeap.peek())/2;
        //奇数个直接去大顶堆top，因为奇数时肯定大顶堆元素多一个
        return maxHeap.peek();
    }
}

这篇关于Heap 相关的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！