前言
优先队列是JAVA以堆排序为基础实现的数据结构,这种结构在删除或新增元素后,会自动进行重排,非常方便。本文分析优先队列中的常用方法源码来加强理解。
堆排序
所谓堆,是一种完全二叉树。如果这颗树的父节点值大于等于子节点值,则称为大顶堆。如果父节点值小于等于子节点,则成为小顶堆。
算法
1、将序列中的n个元素构造成堆
2、堆顶与序列末尾元素交换,这样末尾元素就成了整个序列的最大(最小)值
3、对当前序列的前n-1个元素重复1和2
有关堆排序的详解可以参考这篇文章。
源码解析
变量
1 | //默认容量11 |
对offer()、poll()、remove()这3个方法及它们的关联方法进行分析,其他方法都很简单,直接看源码即可。
offer(E e)
方法
增加元素
每次调用offer()方法时,队列已经是堆的状态的了,offer的元素先假定放在队尾,然后自下向上重构堆
1 | public boolean offer(E e) { |
siftUp(int k, E x)
自下向上 重构堆
1 | private void siftUp(int k, E x) { |
grow(int minCapacity)
扩容的方法
1 | private void grow(int minCapacity) { |
poll()
方法
每次取出队首元素后,假定队尾元素放置队首,然后自上向下重构堆
1 | public E poll() { |
siftDown(int k, E x)
自上向下 重构堆
1 | private void siftDown(int k, E x) { |
从上述代码中可以看出,调用poll()
之后,重构堆时,只是保证了堆顶元素最小,但是左右孩子结点的大小关系不一定,所以底层数组不一定是完全有序的。这本来也是堆结构的性质。我们用一段代码来验证。
1 | PriorityQueue<Integer> queue=new PriorityQueue<>(); |
remove(Object o)
方法
删除指定元素
1 | public boolean remove(Object o) { |
removeAt(int i)
删除指定位置元素
1 | private E removeAt(int i) { |
参考文章
https://www.cnblogs.com/chengxiao/p/6129630.html
发布时间: 2021-02-15
最后更新: 2021-02-16
本文标题: JAVA源码详解之优先队列PriorityQueue(逐行注释)
本文链接: https://eziozhao.com/article/f6a391.html
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处!
