堆

介绍

大顶堆：根节点（堆顶元素）是所有节点中的最大值（父节点都大于左右子节点）。常用于实现优先队列，构建堆排序算法。升序，第k大，前k高
小顶堆：小顶堆中的根节点是所有节点中的最小值（父节点都小于左右子节点）。常用于查找流中的前K个最小元素。降序

Binary Heapconstruction O(n)
Polling O(log(n))
Peeking O(1)
Adding O(log(n))

Naive Removing O(n)
Advanced removing withhelp from a hash table O(log(n))
Naive contains O(n)
Contains check withhelp of a hash table O(1)

• 使用哈希表来帮助优化这些操作确实会占用线性空间，并且还会给二叉堆实现增加一些开销。

t215数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
时间复杂度为 O(n) 的算法解决此问题。
示例 1: 输入: [3,2,1,5,6,4], k = 2 输出: 5

时间复杂度：O(nlogn)，建堆的时间代价是 O(n)，删除的总代价是 O(klogn)，
因为 k<n，故渐进时间复杂为 O(n+klogn)=O(nlogn)。
空间复杂度：O(logn)，即递归使用栈空间的空间代价。
class Solution {
    public int findKthLargest(int[] nums, int k) {
        for(int i=nums.length/2-1;i>=0;i--){
            adjustHeap(nums,i,nums.length);
        }
        for(int i=nums.length-1;i>nums.length-k;i--){
            int temp = nums[i];
            nums[i] = nums[0];
            nums[0] = temp;
            adjustHeap(nums,0,i);
        }
        return nums[0];
    }

    public static void adjustHeap(int[] nums,int i, int len){
        int temp = nums[i];
        for(int k=2*i+1;k<len;k=2*k+1){
            if(k+1<len && nums[k] < nums[k+1]){
                k++;
            }
            if(nums[k] > temp){
                nums[i] = nums[k];
                i=k;
            }else{
                break;
            }
        }

        nums[i] = temp;
    }
}

347前K个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。可以按任意顺序返回答案。
示例 1:输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]
示例 2:输入: nums = [1], k = 1 输出: [1]

思路比较的条件可以是大小也可以是频率
时间复杂度：O(n)，n 表示数组的长度。
遍历一遍数组统计元素的频率时间复杂度 O(n)；
桶的数量为 n+1，所以桶排序的时间复杂度为 O(n)；
因此，总的时间复杂度是 O(n)。
空间复杂度：很明显为 O(n)

class Solution {
    Map<Integer, Integer> map = new HashMap<>();

    public int[] topKFrequent(int[] nums, int k) {
        // 统计每个数字的出现频率
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 把所有不同的数字放到一个数组里，方便后续操作
        int[] uniqueNums = new int[map.size()];
        int index = 0;
        for (int num : map.keySet()) {
            uniqueNums[index++] = num;
        }

        // 构建大根堆
        for (int i = uniqueNums.length / 2 - 1; i >= 0; i--) {
            adjustHeap(uniqueNums, i, uniqueNums.length);
        }

        // 取出前 k 个频繁的数字
        for (int j = uniqueNums.length - 1; j >= uniqueNums.length - k; j--) {
            int temp = uniqueNums[j];
            uniqueNums[j] = uniqueNums[0];
            uniqueNums[0] = temp;
            adjustHeap(uniqueNums, 0, j);
        }

        // 返回结果
        int[] result = new int[k];
        System.arraycopy(uniqueNums, uniqueNums.length - k, result, 0, k);
        return result;
    }

    private void adjustHeap(int[] arr, int i, int len) {
        int temp = arr[i];
        for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
            if (k + 1 < len && map.get(arr[k + 1]) > map.get(arr[k])) {
                k++;
            }
            if (map.get(arr[k]) > map.get(temp)) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;
    }
}

295数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
示例 1：
输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出 [null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

时间复杂度：addNum: O(logn)，其中 n 为累计添加的数的数量。findMedian: O(1)。
空间复杂度：O(n)，主要为优先队列的开销。

class MedianFinder {
    PriorityQueue<Integer> queMin;
    PriorityQueue<Integer> queMax;

    public MedianFinder() {
        queMin = new PriorityQueue<Integer>((a, b) -> (b - a));//小顶堆
        queMax = new PriorityQueue<Integer>((a, b) -> (a - b));//大顶堆
    }
    
    public void addNum(int num) {
        if (queMin.isEmpty() || num <= queMin.peek()) {
            queMin.offer(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.offer(queMin.poll());
            }
        } else {
            queMax.offer(num);
            if (queMax.size() > queMin.size()) {
                queMin.offer(queMax.poll());
            }
        }
    }
    
    public double findMedian() {
        if (queMin.size() > queMax.size()) {
            return queMin.peek();
        }
        return (queMin.peek() + queMax.peek()) / 2.0;
    }
}