LeetCode Heap系列（一）

Heap

堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于） C 的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。

堆可以理解成一个二叉树，而这个二叉树的性质是父节点总是大于或小于子节点。

703. Kth Largest Element in a Stream

题目大意是找到数组中第k大的元素，每次添加元素的时候也都返回第k大的元素。

class KthLargest {
    private PriorityQueue<Integer> q;
	private int k;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        q = new PriorityQueue<>();
	    for(int i : nums) {
	    	add(i);
	    }
    }
    public int add(int val) {
        q.add(val);
		if(q.size() > k) {
			q.remove();
		}
		return q.peek();
    }
   
}

973. K Closest Points to Origin

题目大意是找到一系列点中距离原点最近的k个点。
同样用上面最小堆的思想将点保存到优先队列中。

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        PriorityQueue<Point> q = new PriorityQueue<>();
        int[][] res = new int[K][2];
        int n = points.length;
        for(int i=0; i < n; i++) {
            int[] t = points[i];
            int square = t[0]*t[0] + t[1]*t[1];
            Point p = new Point(i, square);
            q.add(p);
           
        }
        for(int i=0; i<K; i++) {
            res[i] = points[q.peek().posi];
            q.remove();
        }
        return res;
    }
    
    class Point implements Comparable<Point> {
        private int square;   //距离的平方
        private int posi;     // 第几个点
        public Point(int posi, int square) {
            this.posi = posi;
            this.square = square;
        }
		public int compareTo(Point o) {	
			return this.square - o.square;
		}
    }
}

451. Sort Characters By Frequency

题目大意是按照字符串中重复字母数来输出字符串，重复越多越靠前，不考虑相同次数的顺序。
还是利用优先队列次数多的排前面的思路，用HashMap用来保存字符以及统计它出现的次数。discuss里的用优先队列的写法比我的好太多，简练很多，于是最后改成用他那种写法。

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int n = s.length();
        for(int i=0; i<n; i++) {
            char t = s.charAt(i);
            map.put(t, map.getOrDefault(t, 0) + 1);
        }
        
        PriorityQueue<Map.Entry<Character, Integer>> q = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
	    q.addAll(map.entrySet());
         StringBuilder sb = new StringBuilder();
         while (!q.isEmpty()) {
            Map.Entry e = q.poll();
            for (int i = 0; i < (int)e.getValue(); i++) 
                sb.append(e.getKey());
        }
        return sb.toString();
    }
 
}，

347. Top K Frequent Elements

题目大意是求前k个出现最频繁的元素，要求时间复杂度不超过O(nlogN)。
这题和上面那个统计重复字母数有点类似，统计频次时存入map的操作时间复杂度是O(n)，再放入优先队列中时间复杂度是O(nlogN)，所以总的还是不超过题目要求的，照着上面的模子就可以写出如下代码：

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        for(int i=0; i<n; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
        for(Integer key : map.keySet()) {
            q.add(key);
            if(q.size()>k) {
                q.poll();
            }
        }
        List<Integer> list = new LinkedList<>();
        while(!q.isEmpty()) {
            list.add(q.poll());
        }
        Collections.reverse(list);
        return list;
    }
}