优先队列使用

Java和c++已经实现了优先队列，在使用的时候直接调用即可。不过我们现在在学数据结构，可以对优先队列进行扩充，书上的优先队列似乎太低级了，可以寻找更高级的数据结构去实现优先队列；

优先队列在操作系统的任务调度中使用；

后面在学完树结构的时候，最好用堆来实现优先队列；

优先队列的作用是能保证每次取出的元素都是队列中权值最小的

优先队列常用的方法有

public boolean add(E e); //在队尾插入元素，插入失败时抛出异常，并调整堆结构
public boolean offer(E e); //在队尾插入元素，插入失败时抛出false，并调整堆结构

public E remove(); //获取队头元素并删除，并返回，失败时前者抛出异常，再调整堆结构
public E poll(); //获取队头元素并删除，并返回，失败时前者抛出null，再调整堆结构

public E element(); //返回队头元素（不删除），失败时前者抛出异常
public E peek()；//返回队头元素（不删除），失败时前者抛出null

public boolean isEmpty(); //判断队列是否为空
public int size(); //获取队列中元素个数
public void clear(); //清空队列
public boolean contains(Object o); //判断队列中是否包含指定元素（从队头到队尾遍历）
public Iterator<E> iterator(); //迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

leetcode 23 优先队列

通过优先队列来进行合并，很巧妙

需要使用优先队列很多时候是看不出来的，需要留意。

这里指定了优先队列排序的规则

常用优先队列的情景

973. 最接近原点的 K 个点
——优先队列，默认大根堆
1、建立优先队列pair<int,int>，first为坐标到原点的距离，second为坐标索引
2、根据堆的索引 将坐标元素进行整理

23. 合并K个升序链表
——分治合并
1、写出两链表合并逻辑
2、编写分治合并，根据数组的left和right进行递归结束，二分，合并操作
3、调用分治合并
——利用堆合并
…

347. 前 K 个高频元素
——优先队列（<构建的是大根堆，>构建的是小根堆）
1、哈希表计数
2、创建优先队列pair<int,int> 第一个为数字的值，第二个为数字出现的次数
3、将前k个放入优先队列，当k+1~n个元素，不断取出小根堆的堆顶进行更新
4、将优先队列转为答案向量

692. 前K个高频单词
——优先队列
1、哈希表技术
2、创建优先队列pair<string,int>第一个为单词的值，第二个为单词出现的次数
3、将前k个放入优先队列，当k+1~n个元素，不断取出小根堆的堆顶进行更新
4、将队列的元素取出进行结果返回

767. 重构字符串
——哈希计数+优先队列
1、记录字母的出现次数 和最大的出现次数
2、若存在字母出现次数大于(length+1)/2 则不可行
3、将哈希表转优先队列priority<char,…>，cmp排序基于哈希表计数，构建大根堆
4、优先队列size>1，则取队列高频两个字母进行组合，计数-1，若不为0，继续放入队列
5、优先队列元素剩余一个时记得不要遗漏

895. 最大频率栈
——哈希计数+哈希频率向量维护+最大频率变量
push
1、记录数字出现频率
2、更新数字出现的最大频率
3、构建出现频率 数组
pop
1、根据maxFreq 找到对应的元素列表
2、取向量的尾部 即最后压入向量的元素
3、更新该元素出现频率
4、向量弹出后为空 证明maxFreq不存在val 最大maxFreq改变

295. 数据流的中位数
——大根堆+小根堆
push
1、平衡时往大根堆加入元素——小根堆入，再弹出小根堆最小值放入大根堆
2、不平衡时往小根堆加入元素——大根堆入，再弹出大根堆最大值放入小根堆
pop
1、平衡时返回二者平均
2、不平衡时返回大根堆堆顶

1438. 绝对差不超过限制的最长连续子数组——与滑动窗口结合的最值使用队列解决
——滑动窗口+单调队列
1、申请两个单调队列 维护窗口最大值与最小值
2、滑动窗口指针初始化{
3、维护窗口最大值
4、维护窗口最小值
5、加入元素 right++
6、窗口最大值-最小值超过limit 不断left++
7、更新最大值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67