Java 优先队列自排序时机

今天做算法题，使用到了优先队列数据结构——PriorityQueue，但忘记了它发生自动排序的时机，记录一下。

结论：优先队列只有在元素个数发生变化时才发生自排序，如果只是改变已有元素内容，并不能引发自排序。

实例证明：

1. 优先队列元素类，自定义MC类，包含两个属性，编号No和时间aTime。

class MC {
    int No;
    int aTime;

    MC(int no, int atime) {
        No = no;
        aTime = atime;
    }

}

1. 使用优先队列，自定义优先级规则：先按aTime从小到大排序，再按No从小到大排序

class Solution4 {

    public static void main(String[] args) {

        Queue<MC> queue = new PriorityQueue<>(new Comparator<MC>() {
            @Override
            public int compare(MC o1, MC o2) {
                System.out.println("--Sort--");
                if (o1.aTime < o2.aTime)
                    return -1;
                else if (o1.aTime == o2.aTime) {
                    return o1.No - o2.No;
                } else
                    return 1;
            }
        });
        for (int j = 1; j <= 3; j++) {
            System.out.println("insert:" + j);
            queue.offer(new MC(j, 0));
            queue.stream().forEach(e -> System.out.println("<" + e.No + "," + e.aTime + ">"));
        }
        System.out.println("change peek");
        queue.peek().aTime = 5;
        queue.stream().forEach(e -> System.out.println("<" + e.No + "," + e.aTime + ">"));
    }
}

1. 结果：

insert:1
<1,0>
insert:2
--Sort--
<1,0>
<2,0>
insert:3
--Sort--
<1,0>
<2,0>
<3,0>
change peek
<1,5>
<2,0>
<3,0>

可以看到，当新元素插入时，会引发优先队列自排序。

但是只修改内部元素对象时，却不会引发优先队列自排序（没有将aTime最大的移动到队尾）。

优先队列添加元素源代码：

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    siftUp(i, e);  //这里就是调整堆排序
    size = i + 1;
    return true;
}