简单堆和桶排序（自用）

一、 堆： 了解下就好

（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; } }