PriorityQueue源码分析

techzealot
JCF, java

  1. 本质是一个最小二叉堆,底层使用数组进行存储

    使用到的二叉堆性质:(n为二叉堆节点个数,数组从索引0开始存储,从上到下从左到右从0开始依次编号)

    节点i若有左右孩子，则左孩子索引为(i«1)+1,右孩子索引为(i«1)+2

    第一个叶子结点的索引为size»1,最后一个非叶子节点索引为(size»1)-1

    节点i的父节点为(i-1)»1,若(i«1)+1 >=size(无左孩子)则该节点一定为叶子结点

    叶子结点在数组后半段且从第一个叶子结点开始后续全都是叶子结点

    image-20220823171846035

  2. 初始化注意事项:

    若是有序数据结构只需拷贝数据即可无需堆化

    若是无序集合则需要先拷贝数据再进行堆化

  3. 优先队列不允许null,但允许重复，sift进行到重复元素即会终止(比较大小时使用小于)

  4. null检查

    1.offer,replace调用检查null

    2.从集合初始化时单个元素和传入自定义Comparator的需要检查避免存入null，对于其他场景会在heapify中触发NPE，此处可视为提升性能的一种考量

  5. 若未定义Comparator则要求元素本身实现Comparable,否则会在sift时报ClassCastException,此处需要注意从单元素集合初始化时不会报错但在后续添加第二个元素时就会报错

  6. 堆化算法

    堆化原理:从最后一个非叶子节点(size »> 1) - 1开始依次对所有非叶子节点向下筛选直到根节点 堆化方式有两种:

    1.从上到下上滤:最大操作数=所有结点深度之和,O(nlogn)

    2.从下到上下滤:最大操作数=所有结点高度之和,O(n) 因此采用由下到上下滤

  7. 比较根节点，左孩子，右孩子求最小值思路

    先定义最小节点变量并初始化为左孩子，然后依次与剩余节点比较，若其他节点更小则替换

  8. toArray返回的数组顺序与底层数组相同，不是有序的

  9. 添加元素转换为添加到最后然后上滤，删除元素转换为将最后一个元素替换到根节点然后根节点下滤

  10. 迭代器设计:

    1.迭代器迭代时不是有序输出的，是受底层数组以及迭代器remove方法共同影响;

    2.迭代器的设计思路是若在迭代过程中无删除操作则按底层数组顺序输出，若迭代过程中有删除会分两种情况:

    ①当替换元素上滤到已遍历过的部分时则存入双端队列，待遍历完底层数组后按先进先出接着遍历双端队列里的元素

    ②素若替换元素下滤到未遍历部分则遍历指针减一接着遍历

    3.迭代器删除元素设计思路:若在迭代底层数组时删除元素直接删除上一个索引所在元素，若在迭代队列时删除需要通过记录的上一个元素进行删除