download：开课吧-高薪webGL工程师[2022最新完结无密]
文章参考编程猿java自学it http://www.51xuebc.com
从构造方法到实践练习优先队列
一.导言
我们之前讨论过堆栈和队列。在java中，栈的类是stack，队列的接口是queue。我们通过queue的实现类LinkedList练习了queue的方法，并利用相关知识完成了LeetCode 232题如何用栈实现queue。
大家都知道，像我这种不思进取的人，怎么会突然有想法去学一门在工作中从未用过的课呢？不奇怪，我在做LeetCode 347的时候。Top K高频元素题今天试了几次不知道怎么做。看了一下评论部分，发现这个问题其实应该是用优先级队列来做的，才知道有优先级队列这种东西。
但是，PriorityQueue在某些编程语言中是找不到的。幸运的是，java有。实现优先级队列的类是优先级队列。顾名思义，优先就是优先的意思。
俗话说，很多东西用了才知道。所以今天，我将和你一起玩这个优先队列。
第二，优先级队列
由于我没有下载java8的源代码，PriorityQueue类里有很多英文注释，不方便截图，所以我就直接把代码放在下面了。
什么是优先级队列？
众所周知，放入一个元素是放在队列的末尾，放入一个元素就是取出队列头的元素，也就是我们常说的FIFO。那么什么是优先级队列呢？排队和排队有什么区别？能解决什么样的问题？
优先级队列仍然是顾名思义。优先级队列将根据元素的权重自动排列。也就是说，优先级队列实际上是有反FIFO规则的，但其对外接口仍然是从队列头取元素，在队列尾加元素，没有其他访问方式。它看起来像一个队列。
队列实际上是一个覆盖着队列皮肤的堆。
什么是堆？
Heap通常可以看作一个完整二叉树的数组对象，树中的每个节点不小于(或大于)其左右子节点的值。
如果父节点大于左右子节点的值，则为大顶堆。
如果父节点小于左右子节点的值，则它是一个小的顶部堆。
优先级队列的特征
优先级队列中的元素必须实现内部比较器或外部比较器。
优先级队列具有小顶堆的所有特征，默认为小顶堆。
优先级队列不是线程安全的。
不允许空元素。
队列本身是无序的，但是提取的元素的顺序是有序的。
部分功能来自百度。如有疑问，欢迎评论指正。谢谢你。
基本属性
//序列化相关，可以忽略
private static final long serialVersionUID =-7720805057305804111 l；
//默认情况下没有构造参数时数组的长度
private static final int DEFAULT _ INITIAL _ CAPACITY = 11；
//存储元素的数组队列
瞬态对象[]队列；
//
private int size = 0；
//设置排序策略
私有最终比较器
//
瞬态int mod count = 0；
复制代码
施工方法
我将以下三种构造方法归为一类，第四种构造方法为主，其他三种为方法重载，DEFAULT_INITIAL_CAPACITY为值。队列长度比较器参考优先级排序规则。默认情况下，优先级值很小。
第四种构造方法是初始化队列数组的长度，设置比较器。
公共优先级队列(){
this(DEFAULT_INITIAL_CAPACITY，null)；
}
公共优先级队列(int initialCapacity) {
this(initialCapacity，null)；
}
公共优先级队列(比较器
this(DEFAULT_INITIAL_CAPACITY，比较器)；
}
公共优先级队列(int initialCapacity，
比较仪
if (initialCapacity < 1)
抛出新的IllegalArgumentException()；
this . queue = new Object[initial capacity]；
this.comparator =比较器；
}
复制代码
下面是PriorityQueue构造方法的一个测试。可以发现，当我们调用PriorityQueue.size()方法时，返回的不是我们设置的队列长度，而是元素个数。
下面的施工方法会稍微复杂一点。
//包含优先级元素
公共优先级队列(PriorityQueue
this .比较器=(比较器
initfromporityqueue©；
}
复制代码
下图是上面的构造函数构造的，真的很有意思。大家可以看到，priorityQueue4是按照我们设定的规则降序排列的，没有任何问题。但是priorityQueue5继承了priorityQueue4和比较器的元素后，打印出来的并没有完全按顺序打印，最后四个元素变成了2，1，2，1，2，2，1。
用指定顺序的集合元素创建PriorityQueue。
公共优先级队列(排序集
this .比较器=(比较器
initElementsFromCollection©；
}
复制代码
具体的测试代码如下所示。像PriorityQueue类一样，它是一个继承其类的比较器。
下面的构造方法整合了前面两个构造方法，他们调用的最后一个方法主要是初始化数组，有各种跳转。有兴趣的可以自己看看。
公共优先级队列(集合
if (c已排序集合的实例){
有序集
this .比较器=(比较器
initElementsFromCollection(ss)；
}
else if(c instance of priority queue){
优先级队列
this .比较器=(比较器
initfromporityqueue(pq)；
}
否则{
this.comparator = null
initFromCollection©；
}
}
复制代码
常规方法
添加/提供:添加元素
Element/peek:不删除return元素。
Remove/poll:弹出元素并删除。
删除:删除元素，如果有多个元素，则只删除一个元素。
摘要
有很多东西，你用了才知道。如果可以的话，最好提前了解他们，防止出现我这样的情况:不知道什么时候需要他们。
有什么说法？你用一本书就不那么讨厌了。走吧。