优先级队列(Priority Queue)
优先级队列也是个队列，因此也是有这和队列差不多的设计方法，唯一不同的就是多了一个优先级，普通的队列是遵循FIFO原则，也就是先进先出，优先级队列则是按照优先级高低进行出队，比如将优先级最高的元素作为队头优先出列
优先级队列的应用场景举例
医院的夜间门诊
队列元素是病人
优先级是病情的严重情况，挂号时间
操作系统的多任务调度
队列元素是任务
优先级是任务类型
接口设计
int size();//元素的数量
boolean isEmpty();//是否为空
void enQueue(E element);//入队
E deQueue();//出队
E front;//获取队列的头元素
void clear();//清空
优先队列的底层实现
PriorityQueue
测试图
底层是直接利用二叉堆左右优先队列实现的，通过Person自定义CompareTo方法，比较数字大小，从而定义优先级高低
哈夫曼编码(Huffman Coding)
哈夫曼编码，又称为霍夫曼编码，它是现代压缩算法的基础；
假设现在要把字符串[ABBBCCCCCCCCDDDDDDEE]转成二进制编码进行传输，可以转成ASCII编码(65~69,1000001~1000101),但是会发现结果有点冗长，于是我们可能想到用更短的约定的编码格式来定义，例如：
A:000;B:001;C:010;D:011;E:100,这样我们就可以简单方面的将上面的字符串转换成：
000 001001001 010010010010010010010010010 011011011011011011 100 一共20个字母，转成了60个二进制位，使用哈夫曼编码，可以压缩成更少的二进制位；
哈法曼树
先计算出每个字母出现的频率(权值，这里直接用出现的次数)
权值
利用这些权值，构建一棵哈弗曼树(又称为霍夫曼树，最优二叉树)
1.以权值作为根节点构建n棵二叉树，组成森林
2.在森林中选出2个根节点最小的树合并，并作为一棵新树的左右子树，且新树的根节点为其左右子树根节点之和
3.从森林中删除刚才选取的2棵树，并将新树加入森林
4.重复2，3步骤，知道森林只剩一棵树为止，该树即为哈弗曼树
上面的步骤转化为如下图所示：
构建哈弗曼树
构建哈夫曼编码
哈夫曼树
left为0，right为1，可以得出A，B，C，D，E5个字母对应的哈弗曼编码
构建哈夫曼编码
[ABBBCCCCCCCCDDDDDDEE]的哈夫曼编码是：1110110110110000000001010101010101111
哈夫曼编码总结
n个权值构建出来的哈夫曼树拥有n个叶子节点，每个哈夫曼编码都不是另一个哈夫曼编码的前缀，哈夫曼树是带权路径长度最短的树，权值较大的节点离根节点较近；（带权路径长度：树中所有的子节点的权值乘上其到根节点的路径长度，与最终的哈夫曼编码总长度成正比关系）
Trie
Trie 也叫做字典树，前缀树(Prefix Tree),单词查找树；Trie搜索字符串的效率主要跟字符串的长度有关
Trie 接口设计
Trie接口设计
Trie 展示图
Trie 存放图
上面的展示Trie村粗cat，dog，doggy，does，cast，add6个单词
红色代表单词结束。
Trie实现代码图
构建节点代码
节点构造
parent：删除时候由后往前删除需要用到
HashMap<Character,Node<V>> children;存储对象，Character代表字母作为key，也就是d o g，Node<V>作为value，存储相关子节点数据
Character character：存储的key，删除时候使用
V value:红色节点存储的值，红色节点也代表一个单词介绍
boolean word;是否为单词的结尾，代表单词是否结束
获取node代码
node
会发现之后很多方法都会用到这个node方法，所以这里就不进一步作单词的判断，直接返回node节点按照外面的逻辑进行处理
获取节点方法get和包含方法判断
get&contains
通过word是否为true来判断要寻找的单词是否存在
前缀方法
startsWith
添加方法
add
添加单词方法重点就是如果没有子节点就创建子节点，如果有子节点的话，就判断单词是否存在，存在就替换，不存在就新增
删除方法
remove
删除方法相对于增加方法来说，会稍微麻烦一点，需要判断是否还有子节点，针对子节点是否存在的情况进行相关处理
Trie总结
Trie的优点：搜索前缀的效率主要跟前缀的长度有关
Trie的缺点：需要消耗大量的内存，因此还有待改进(一个字符对应一个节点，二叉树一个单词对应一个节点，所以相对来说内存消耗大)
网友评论