1. 优先级队列（Priority Queue）
(1) 定义
普通队列：FIFO原则，也就是先进先出
优先级队列（Priority Queue）：按照 优先级高低 进行出队
队列
(2) 应用场景
- 夜间门诊
队列元素：病人
优先级：病情的严重情况、挂号时间- 操作系统的多任务调度
队列元素：任务
优先级：任务类型
(3) 底层实现
- 通过 二叉堆 作为优先级队列的底层实现
- 通过 Comparator 或 Comparable 自定义优先级高低
2. 哈夫曼树（Huffman Tree）
(1) 哈夫曼编码（Huffman Coding）
将字符串【ABBBCCCCCCCCDDDDDDEE】转成二进制编码进行传输
1> 方法一：ASCII编码
转成ASCII编码（65 ~ 69，1000001 ~ 1000101），冗长
2> 方法二：约定二进制
约定5个字母对应的二进制：
| A | B | C | D | E |
|---|---|---|---|---|
| 000 | 001 | 010 | 011 | 100 |
对应的二进制编码：
20个字母，转成了60个二进制位
3> 方法三：哈夫曼编码（Huffman Coding）
哈夫曼编码：现代 压缩算法 的基础
可以压缩至41个二进制位，约为原来长度的68.3%
(2) 哈夫曼树（Huffman Tree）
1> 首先计算出每个字母的出现频率（权值）
| A | B | C | D | E |
|---|---|---|---|---|
| 1 | 3 | 8 | 6 | 2 |
2> 构建哈夫曼树（最优二叉树）
如何构建一棵哈夫曼树？（假设有n个权值）
- 以 权值 作为根节点 构建 n棵二叉树，组成森林
- 在森林中选择2个根节点最小的树合并，作为一颗新树的左右子树，且新树的根节点为其左右子树根节点之和
- 从森林中删除刚才选取的2棵树，并将新树加入森林
- 重复2、3步骤，知道森林只剩下一棵树为止，该树即为哈夫曼树
哈夫曼树
3> 构建哈夫曼编码
哈夫曼树
left为0，right为1，可得5个字母对应的哈弗曼编码：
| A | B | C | D | E |
|---|---|---|---|---|
| 1110 | 110 | 0 | 10 | 1111 |
【ABBBCCCCCCCCDDDDDDEE】的哈夫曼编码为：
(3) 总结
- n个权值 构建出来的 哈夫曼树 拥有n个叶子节点
- 每个哈夫曼编码 都不是 另一个哈夫曼编码的 前缀
- 哈夫曼树是 带权路径长度最短的树，权值较大的节点 离根节点较近
带权路径长度：
树中所有的 叶子节点的权值 乘以 其到根节点的路径长度
与最终的哈夫曼编码总长度 成正比关系
3. Trie
(1) 定义
Trie：也叫 字典树、前缀树、单词查找树
Trie 搜索字符串的效率 主要跟字符串的长度 有关
使用Trie存储cat、dog、doggy、does、cast、add六个单词：
Trie
Trie优点：搜索前缀的效率 主要跟 前缀的长度 有关
Trie缺点：需要耗费大量的算法，有待改进
