堆

---

215. 数组中的第K个最大元素

// 方法一：优先队列，初始大小确定，参入参数k
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        for (int num : nums) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (num > pq.peek()) {
                pq.poll();
                pq.offer(num);
            }
        }
        return pq.peek();
    }
}

// 方法二，数组建堆，build一次就可以，不需要排序
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int[] heap = new int[k];
        for (int i = 0; i < k; i++) {
            heap[i] = nums[i];
        }
        buildheap(heap, k);
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > heap[0]) {
                heap[0] = nums[i];
                heapify(heap, 0, k);
            }
        }
        return heap[0];
    }

    public void heapify(int[] nums, int i, int n) {
        int smallest = i;
        int leftchild = 2 * i + 1;
        int rightchild = 2 * i + 2;

        if (leftchild < n && nums[leftchild] < nums[smallest]) {
            smallest = leftchild;
        }
        if (rightchild < n && nums[rightchild] < nums[smallest]) {
            smallest = rightchild;
        }
        if (smallest != i) {
            int temp = nums[i];
            nums[i] = nums[smallest];
            nums[smallest] = temp;
            heapify(nums, smallest, n);
        }
    }

    public void buildheap(int[] nums, int n) {
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(nums, i, n);
        }
    }
}

347. 前 K 个高频元素

// HashMap和PriorityQueue，默认小顶堆即可，构造优先队列传入比较器
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ans = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // entrySet()
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num = entry.getKey(), cnt = entry.getValue();
            if (pq.size() < k) {
                pq.offer(num);
            } else if (cnt > map.get(pq.peek())) {
                pq.poll();
                pq.offer(num);
            }
        }
        for (int i = 0; i < k; i++) {
            ans[i] = pq.poll();
        }
        return ans;
    }
}

// 遍历HashMap可以使用forEach的lambda表达式
// map.forEach((key, value) -> {
//     if (pq.size() < k) {
//         pq.offer(key);
//     } else if (value > map.get(pq.peek())) {
//         pq.poll();
//         pq.offer(key);
//     }
// });