12.Java SDK源码分析系列笔记-PriorityQueue

龙玮奇 · 7 天前

1. PriorityQueue是什么
2. 使用
3. 源码分析
- 3.1. 属性
- 3.2. 有参构造
  - 3.2.1. 初始化元素到数组中
  - 3.2.2. 维护堆的属性
    - 3.2.2.1. 下沉操作
- 3.3. 插入
  - 3.3.1. 上浮操作
- 3.4. 删除
  - 3.4.1. 下沉操作
4. 参考

1. PriorityQueue是什么

是一个队列，只不过加上了优先级的概念，换句话说队列里的元素是根据某种规则排好序的
2. 使用

public class PriorityQueueTest
{
public static void main(String[] args)
{
List<Integer> list = Arrays.asList(20, 19, 18, 17, 16, 15, 14, 13, 12, 11);
PriorityQueue<Integer> queue = new PriorityQueue<>(list);
System.out.println("最开始的元素：" + queue);
System.out.println("============");
queue.offer(11);
System.out.println("添加了一个11：" + queue);
System.out.println("============");
List<Integer> sort = new ArrayList<>();
while (!queue.isEmpty())
{
Integer poll = queue.poll();
System.out.println("堆顶是：" + poll);
sort.add(poll);
System.out.println("剩余的元素：" + queue);
System.out.println("----------");
}
System.out.println("============");
System.out.println("堆排序的结果：" + sort);
}
}

复制代码

输出

最开始的元素：[11, 12, 14, 13, 16, 15, 18, 20, 17, 19]
============
添加了一个11：[11, 11, 14, 13, 12, 15, 18, 20, 17, 19, 16]
============
堆顶是：11
剩余的元素：[11, 12, 14, 13, 16, 15, 18, 20, 17, 19]
----------
堆顶是：11
剩余的元素：[12, 13, 14, 17, 16, 15, 18, 20, 19]
----------
堆顶是：12
剩余的元素：[13, 16, 14, 17, 19, 15, 18, 20]
----------
堆顶是：13
剩余的元素：[14, 16, 15, 17, 19, 20, 18]
----------
堆顶是：14
剩余的元素：[15, 16, 18, 17, 19, 20]
----------
堆顶是：15
剩余的元素：[16, 17, 18, 20, 19]
----------
堆顶是：16
剩余的元素：[17, 19, 18, 20]
----------
堆顶是：17
剩余的元素：[18, 19, 20]
----------
堆顶是：18
剩余的元素：[19, 20]
----------
堆顶是：19
剩余的元素：[20]
----------
堆顶是：20
剩余的元素：[]
----------
============
堆排序的结果：[11, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Process finished with exit code 0

复制代码

3. 源码分析

3.1. 属性

[code]public class PriorityQueue extends AbstractQueue implements java.io.Serializable { private static final long serialVersionUID = -7720805057305804111L; //默认的大小为11 private static final int DEFAULT_INITIAL_CAPACITY = 11; //二叉堆：物理上是个数组，逻辑上看成二叉树 transient Object[] queue; // non-private to simplify nested class access //容量 private int size = 0; //比较器，用来确定插入的元素在二叉堆中的位置 private final Comparator

账号		自动登录	找回密码
密码			立即注册