Java中的PriorityQueue

PriorityQueue底层是使用数组实现完全二叉树的二叉堆，默认是最小堆。通过数组索引维护父子节点

特点

1. 底层使用数组存储数据，存储空间连续，可根据索引位快速访问
2. 使用自然排序：元素必须实现Comparable接口
3. 使用自定义排序：创建PriorityQueue传入比较器
4. 元素排序：是父节点与子节点比较来排序，最小堆是父节点必须小于等于子节点；最大堆是父节点必须大于等于子节点
5. 节点顺序：只保证父节点与子节点的顺序，左右子节点不保证顺序
6. 元素不能为空：传入null值会报空指针异常
7. 每次获取元素都是从数组头部获取，每次添加元素都是添加在数组尾部
8. 可以删除任意节点的元素(删除元素不用移动元素位置)
9. 扩容：默认数组容量是11，当数组满了会进行扩容，旧容量小于64，则扩容到原来的倍+2；数组容量大于等于64，扩容到原来的1.5倍(扩容后直接把原数组数据复制到新数组)

添加节点流程

每次添加元素都是往数组尾部添加元素，之后上浮比较元素，父节点比子节点小就一直交换，直到根节点

1. 添加的元素所在索引位是k
   1. 第一次添加，没有父节点，直接添加
   2. 后续添加，使用索引位k推算出父节点的位置
      1. 与父节点比较
         1. 比父节点大：直接写入索引位k
         2. 比父节点小：与父节点交换位置存储
2. 将父节点索引位变成k，继续以上步骤，直到k<=0

删除节点流程

删除时，下沉比较元素，完成首次删除换位后，如果删除元素的索引位i有子节点，循环比较

删除节点时：

1. 获取到数组尾部的节点：尾部索引为s
2. 将尾部索引位置为null
3. 根据数组元素个数计算出half(half是第一个没有子节点的位置)
4. 要删除的节点索引位为i
5. 推算出i索引位节点的左右子节点left，right
6. 根据删除节点索引位i与尾部父节点half比较
   1. while循环i<half
      1. 另一个放入选出的left或者right位置
      2. 小的那个放入要删除的索引位i
      3. 较小的那个(left或者right)与尾部节点元素比较大小
      4. i的左右子节点比较大小，选出小的那个
      5. left或者right节点变成i，继续循环，直到i>=half
   2. i>=half(i索引位没有子节点)
      1. 直接用尾节点元素替换到i位置

第一种情况

第二种情况

 第三种情况

 弹出节点流程

每次弹出数组首部元素

1. 获取到首部元素
2. 获取到数组尾部元素
3. 将尾部索引位置为null
4. 根据数组元素个数确认half((half是第一个没有子节点的位置))
5. 确认首部元素的左右子节点left，right
6. while循环i<half
   1. 另一个放入选出的left或者right位置
   2. 小的那个放入要删除的索引位i
   3. 较小的那个(left或者right)与尾部节点元素比较大小
   4. i的左右子节点比较大小，选出小的那个
   5. left或者right节点变成i，继续循环，直到i>=half
7. i>=half(i索引位没有子节点)
   1. 直接用尾节点元素替换到i位置

第一种情况

第二种情况 

应用场景

任务调度：根据定义的顺序，每次获取的都是优先级最高的任务