深入理解Java PriorityQueue

忘是亡心i 2022-03-06 05:28 202阅读 0赞

底层代码实现原理参考链接：  
[https://www.cnblogs.com/CarpenterLee/p/5488070.html][https_www.cnblogs.com_CarpenterLee_p_5488070.html]

**PriorityQueue**  
PriorityQueue 是一个基于优先级堆（？？？）的无界队列，它的元素是按照自  
然顺序(natural order)**（解释：从小到大的顺序**）排序的。在创建的时候，我们可以给它提供一个负责给元素排序的比较器。**PriorityQueue 不允许null 值**，因为他们没有自然顺序，或者说他  
们没有任何的相关联的比较器。最后，**PriorityQueue 不是线程安全的**，入队和出  
队的时间复杂度是O(log(n))（解释：因为是完全二叉树，所以树的高度是logn）。  
堆树的定义如下：  
（1）堆树是一颗完全二叉树；  
（2）堆树中某个节点的值总是不大于或不小于其孩子节点的值；  
（3）堆树中每个节点的子树都是堆树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjQxOTU3_size_16_color_FFFFFF_t_70]  
**1. 添加元素add()和offer()**(**解释：** PriorityQueue底层数据结构是最小堆，当然了我们只需要会用就行，没必要管它底层是怎么存储的，原理如下也讲的很详细)  
**原理：** 添加元素位于末尾，同时队列长度加1，然后这个元素与它的父节点进行比较，如果比父节点小那么就与父节点进行交换，然后再与交换后的位置的父节点进行比较，重复这个过程，直到该元素的值大于父节点结束这个过程。  
**区别:** add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue 接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。对于PriorityQueue 这两个方法其实没什么差  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjQxOTU3_size_16_color_FFFFFF_t_70 1]  
**2. 寻找队列的头部元素element()和peek()头部元素时间复杂度为1**  
element()和peek()的语义完全相同，都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别是当方法失败时前者抛出异常，后者返回null。根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由于堆用数组表示，根据下标关系，0 下标处的那个元素既是堆顶元素。所以直接返回数组0 下标处的那个元素即可。

**3.删除元素remove() 和poll()**  
区别:remove()和poll()方法的语义也完全相同，都是获取并删除队首元素，区别是当方法  
失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护小顶堆的  
性质，需要进行必要的调整。  
原理：该方法的作用是从k 指定的位置开始，将x 逐层向下与当前点的左右孩子中较小的  
那个交换，直到x 小于或等于左右孩子中的任何一个为止  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjQxOTU3_size_16_color_FFFFFF_t_70 2]

[https_www.cnblogs.com_CarpenterLee_p_5488070.html]: https://www.cnblogs.com/CarpenterLee/p/5488070.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjQxOTU3_size_16_color_FFFFFF_t_70]: /images/20220306/373e7b962a774d1eb829621c4922e9cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjQxOTU3_size_16_color_FFFFFF_t_70 1]: /images/20220306/7cdb13aa151c4d8284534f75071191e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjQxOTU3_size_16_color_FFFFFF_t_70 2]: /images/20220306/ca32735ba52d417d9c2a2086ca969d39.png