java在向优先级队列添加值时，值是在什么时候排序的？

Question

考虑这个伪代码：

PriorityQueue <Integer> pq = new PriorityQueue(new Comparator()
{
    public int compare(Object o1, Object o2) 
    {
         Integer e1 = (Integer)o1;
         Integer e2 = (Integer)o2;
         if (e1 > e2) {return -1;}
         if (e2 > e1) {return 1;}
         return 0;
     }
});

pq.add(4);
pq.add(7);
pq.add(5);
pq.add(2);
pq.add(9);

现在我想知道，队列在运行时什么时候运行compare（）方法？我假设它将遵循以下顺序：

i）首先，按顺序将数字4、7、5、2、9添加到队列中

ii）然后优先级队列使用比较方法对值进行排序

换句话说，值首先插入队列中。然后对它们进行排序。这种想法正确吗？或者在将值添加到队列中时对其进行排序

Answer 1

优先级队列不像排序数组那个样是一种简单的排序数据结构。 java中的PriorityQueue是使用优先级堆实现的。您应该了解堆是如何工作的，但基本上当您添加新元素时，会发生最大日志（n）比较。没有必要对所有元素进行相互比较。您可以在https://en.m.wikipedia.org/wiki/Priority_queue了解有关优先级队列的更多信息

Answer 2

PriorityQueue类具有为插入顺序（private final Comparator<? super E> comparator）定义的私有字段Comparator）。。。所以当你这样做的时候：

PriorityQueue<Integer> pq = new PriorityQueue<>(foo);

当foo是比较器的实例时，该对象将在该实例内部初始化

创建集合后，开始向其中添加元素，这就是神奇之处

只需查看PriorityQueue类内部，您将找到将被调用的方法siftUpUsingComparator，并使用您定义的比较器验证插入顺序

private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

---

离题：

您使用的是原始集合，这很糟糕，我建议您将代码调整为以下内容：

Comparator<Integer> foo = (o1, o2) -> {
    Integer e1 = o1;
    Integer e2 = o2;
    if (e1 > e2) {
        return -1;
    }
    if (e2 > e1) {
        return 1;
    }
    return 0;
};
PriorityQueue<Integer> pq = new PriorityQueue<>(foo);

pq.add(4);
pq.add(7);
pq.add(5);
pq.add(2);
pq.add(9);