12.Java SDK源码分析系列笔记-PriorityQueue
目录[*]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：
============
堆顶是：11
剩余的元素：
----------
堆顶是：11
剩余的元素：
----------
堆顶是：12
剩余的元素：
----------
堆顶是：13
剩余的元素：
----------
堆顶是：14
剩余的元素：
----------
堆顶是：15
剩余的元素：
----------
堆顶是：16
剩余的元素：
----------
堆顶是：17
剩余的元素：
----------
堆顶是：18
剩余的元素：
----------
堆顶是：19
剩余的元素：
----------
堆顶是：20
剩余的元素：[]
----------
============
堆排序的结果：
Process finished with exit code 03. 源码分析
3.1. 属性
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
页:
[1]