一、 堆： 了解下就好
（1）堆是完全二叉树的结构
什么是完全二叉树：
1.只允许最后一行不满
2.最后一行必须从左往右排，中间不能有间隔
（2）堆序性
1.小根堆，父节点都要更小
2.大根堆，父节点都要更大
（3）堆的存储，因为是完全二叉树，所以可以根据层序遍历，来得到一个数组，此时，父节点为i时，左右子节点一定为2i+1/2
（4）堆有两个基本操作:
1.上滤，通常用于插入新元素到根中时，向上调整位置时
2.下滤(因为必须要满足堆序性的话，所以对不满足的要操作)，把根节点向下调整的操作叫下滤
（5）自顶向下建堆法:
1.插入堆
2.上滤
（6）自下而上建堆法:
对每个父节点进行下滤(从最下面的父节点开始)--复杂度O(N)
（7）应用
1.优先队列:弹出最小元素--可以用来实现堆排序，用大根堆排序完，弹出的是正序，小根堆反
2.插入:就是上滤
java中常见写法
最大堆：（Lamda）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);最小堆：
一般直接这么写就行
PriorityQueue<Integer> small_stack = new PriorityQueue<>();lamda
二、桶排序
例题：前K个高频元素
class Solution { public int[] topKFrequent(int[] nums, int k) { // 第一步：统计每个元素的出现次数 Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) { cnt.merge(x, 1, Integer::sum); // cnt[x]++ } int maxCnt = Collections.max(cnt.values()); // 第二步：把出现次数相同的元素，放到同一个桶中 List<Integer>[] buckets = new ArrayList[maxCnt + 1]; Arrays.setAll(buckets, _ -> new ArrayList<>()); for (Map.Entry<Integer, Integer> e : cnt.entrySet()) { buckets[e.getValue()].add(e.getKey()); } // 第三步：倒序遍历 buckets，把出现次数前 k 大的元素加入答案 int[] ans = new int[k]; int j = 0; for (int i = maxCnt; i >= 0 && j < k; i--) { // 注意题目保证答案唯一，一定会出现某次循环结束后 j 恰好等于 k 的情况 for (int x : buckets[i]) { ans[j++] = x; } } return ans; } }
