目录
1.优先级队列（堆）概念：
1.2现实中的优先级队列PriorityQueue
1.2.1手术排期
1.2.2操作系统的任务调度
编辑
2.堆（heap，基于二叉树）
2.1堆逻辑上是一颗完全二叉树
2..2关于节点值
2.3关于下标
3.堆的基础表示
3.1向堆中添加元素siftup
3.2在堆中取出最大值（最大堆）
4.heapify - 堆化
5.在java中比较两个元素的大小关系：
6.堆的应用-优先级队列（Topk问题）
6.1概念
6.2应用
1.优先级队列（堆）概念：
按照优先级的大小动态出队（动态指的是元素个数动态变化，而非固定）。
普通队列：FIFO。按照元素的入队顺序出队，先入先出。
1.2现实中的优先级队列PriorityQueue
1.2.1手术排期
1.2.2操作系统的任务调度
2.堆（heap，基于二叉树）
2.1堆逻辑上是一颗完全二叉树
2.1堆逻辑上是一颗完全二叉树
（不用存储空节点值）
2..2关于节点值
2.3关于下标
3.堆的基础表示
3.1向堆中添加元素siftup
3.2在堆中取出最大值（最大堆）
4.heapify - 堆化
5.在java中比较两个元素的大小关系：
6.堆的应用-优先级队列（Topk问题）
6.1概念
在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。
在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级的对象，一个是添加新的对象。这种数据结构就是优先级队列（PriorityQueue）
6.2应用
public int[] smallestK(int[] arr, int k) {
int[] ret = new int[k];
if (arr.length == 0 || k == 0) {
return ret;
}
// JDK默认是一个最小堆,需要改成一个最大堆
// Lambda表达式
Queue queue = new PriorityQueue<>((o1,o2) -> o2 - o1);
// Queue queue = new PriorityQueue<>(new Comparator() {
// @Override
// public int compare(Integer o1, Integer o2) {
// return o2 - o1;
// }
// });
// 遍历原集合，队列只保存k个元素
for (int i = 0; i < arr.length; i++) {
if (queue.size() < k) {
queue.offer(arr[i]);
}else {
int max = queue.peek();
if (arr[i] < max) {
queue.poll();
queue.offer(arr[i]);
}
}
}
// 此时队列中就保存了前k个最小值元素,依次出队即可
int i = 0;
while (!queue.isEmpty()) {
ret[i ++] = queue.poll();
}
return ret;
}
public class LC347TokFreqNum {
public int[] topKFrequent(int[] nums, int k) {
int[] ret = new int[k];
// 1.先扫描原数组，将出现的元素以及其频次保存到Map集合中。
// [1,1,1,2,2,3] => {{1 : 3},{2 : 2}, {3 : 1} }
Map map = new HashMap<>();
for (int i : nums) {
// if (map.containsKey(i)) {
// // 此时元素i已经出现过，只要将频次 ++ 即可
// int times = map.get(i);
// map.put(i,times + 1);
// }else {
// // 此时i第一次出现，就将该元素保存到map中
// map.put(i,1);
// }
// 若i对应的元素在Map中不存在，返回0 + 1
map.put(i,map.getOrDefault(i,0) + 1);
}
// 2.扫描Map集合，将出现频次最高的前k个元素添加到优先级队列中
Queue queue = new PriorityQueue<>();
for (Map.Entry entry : map.entrySet()) {
if (queue.size() < k) {
queue.offer(new Freq(entry.getKey(),entry.getValue()));
}else {
// 判断堆顶元素和当前元素的出现频次
// 只有当前元素的出现频次 > 堆顶元素，入队，打擂思想，不断将出现频次大的元素对换入到队列中
Freq freq = queue.peek();
if (entry.getValue() > freq.value) {
queue.poll();
queue.offer(new Freq(entry.getKey(),entry.getValue()));
}
}
}
// 3.此时队列中就保存了出现频次最大的前k个数对 - k个Freq对象
// 遍历队列，将Freq对象中的key取出放入结果集中即可
int i = 0;
while (!queue.isEmpty()) {
ret[i ++] = queue.poll().key;
}
return ret;
}
}
class Freq implements Comparable {
// 数组中出现的元素
int key;
// 该元素出现的频次
int value;
public Freq(int key, int value) {
this.key = key;
this.value = value;
}
@Override
public int compareTo(Freq o) {
return this.value - o.value;
}
}
public class LC373_KSmallestPairs {
public List> kSmallestPairs(int[] nums1, int[] nums2, int k) {
//1.创建优先级队列，其中队列中保存比较对象，传入比较器，和越小反而越大
Queue queue = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Pair o1, Pair o2) {
return (o2.u + o2.v) - (o1.u + o1.v);
}
});
//2.遍历两个数组，其中u来自第一个数组，v来自第二个数组
//队列中保存了和最小的k个数对
for (int i = 0;i < Math.min(nums1.length, k);i++){
for (int j = 0;j < Math.min(nums2.length, k);j++){
if (queue.size() < k){
queue.offer(new Pair(nums1[i],nums2[j]));
}else{
int add = nums1[i] + nums2[j];
Pair pair = queue.peek();
if (add < (pair.u + pair.v)){
queue.poll();
queue.offer(new Pair(nums1[i],nums2[j] ));
}
}
}
}
// 3.此时队列中就保存了和最小的前k个Pair对象，取出其中u和v即可
List> ret = new ArrayList<>();
while (!queue.isEmpty()) {
List temp = new ArrayList<>();
Pair pair = queue.poll();
temp.add(pair.u);
temp.add(pair.v);
ret.add(temp);
}
return ret;
}
}
class Pair{
int u;
int v;
public Pair(int u,int v) {
this.u = u;
this.v = v;
}
}
