取一堆数里面的最小值

Specify特殊Class的Heap

        PriorityQueue<Cell> q = new PriorityQueue<Cell>(m*n,new Comparator<Cell>(){
            @Override 
            public int compare(Cell c1,Cell c2){
                return c1.h - c2.h;
            }
        });

O(1) Insertion O(N) search

Maximum K / Top K 维护一个大小为K的

Top K 问题

347. Top K Frequent Elements

Build a HashMap recording the frequency and a max Heap that polls according the value of the HashMap entry

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        if(nums == null)return null;
        List<Integer> res = new ArrayList<Integer>();
        //Find the frequency of each element
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int num: nums){
            if(!map.containsKey(num))
                map.put(num, 1);
            else
                map.put(num, map.get(num)+1);
        }
        //customized the max heap
        PriorityQueue<Map.Entry<Integer,Integer>> q = new PriorityQueue<Map.Entry<Integer,Integer>>(new Comparator<Map.Entry<Integer,Integer>>(){
            @Override
            public int compare(Map.Entry<Integer, Integer> p1,Map.Entry<Integer, Integer> p2){
                return p2.getValue()-p1.getValue();
            }
        });
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            q.add(entry);
        }
        for(int i = 0;i < k;i++){
            Map.Entry<Integer, Integer> entry = q.poll();
            res.add(entry.getKey());
        }
        return res;
    }
}

215. Kth Largest Element in an Array

public class Solution {
    public int findKthLargest(int[] nums, int k) {
     PriorityQueue<Integer> q = new PriorityQueue<>();
     //put all elements in q
     int len = nums.length;
     for(int i = 0;i < len;i++){
         q.add(nums[i]);
         while(q.size() > k){
             q.poll();
         }
     }
     return q.peek();
    }
}

Two Heaps

295. Find Median from Data Stream

想一想是怎么算Median的 和左右两边有关 我们可以获得左边的最大和右边的最小 维护两个Heap 并且保持两边的元素个数相差不超过 1

public class MedianFinder {
    PriorityQueue<Integer> qMin;
    PriorityQueue<Integer> qMax;
    public MedianFinder(){
        qMin = new PriorityQueue<Integer>();
        qMax = new PriorityQueue<Integer>(Collections.reverseOrder());
    }
    // Adds a number into the data structure.
    public void addNum(int num) {
        if(qMin.isEmpty() || num > qMin.peek()){
            qMin.offer(num);
        }
        else {
            qMax.offer(num);
        }
        //Balance Two Heaps
        while(Math.abs(qMin.size() - qMax.size()) > 1){
            if(qMax.size() > qMin.size()){
                qMin.offer(qMax.poll());
            } 
            else {
                qMax.offer(qMin.poll());
            }
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        int maxSize = qMax.size();
        int minSize = qMin.size();
        if(qMax.size() == qMin.size()){
             return (double)(qMax.peek()+qMin.peek())/2.0;
        }
        //分情况讨论
        if(maxSize - 1 == minSize) return (double) qMax.peek();
        if(maxSize == minSize - 1) return (double) qMin.peek();
        return 0;

    }
}

Specify Your Priority Queue

1. With HashMap Entry

PriorityQueue<Map.Entry<Character, Integer>> q = 
                         new PriorityQueue<>((a,b)->(b.getValue()-a.getValue()));

451. Sort Characters By Frequency

1. With array entry

Comparator<int[]> comparator = new Comparator<int[]>(){
            public int compare(int[] arr1, int[] arr2) {
                return (arr2[0] + arr2[1]) - (arr1[0] + arr1[1]);
            }
        };
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(3, comparator);

373. Find K Pairs with Smallest Sums

Kth Smallest Sum In Two Sorted Arrays

转化问题

Trapping Rain Water II

灌水问题 重要思路是从外面往里面灌水 取最小值用Heap 以及用标记法区分外面和里面 每次放到Heap里面是柱子加上水的高度

O(N) Every Cell is traversed once