将值添加到优先级队列时，何时对值进行排序？

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（）方法？我以为，它会按照这个顺序：

我）首先，数字4,7,5,2,9将被添加到队列的顺序

II）则优先级队列使用的比较方法排序的值

换句话说，该值被首先插入到队列中。然后他们被排序。这个想法是否正确？还是值被排序，因为他们被添加到队列？

Answer 1

PriorityQueues不类似种类排序数组的简单排序的数据结构。 Java中的PriorityQueue是使用优先级堆实现的。您应该了解堆是如何工作的，但基本上当您添加新元素时，会发生最大log（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; 
} 

---

Offtopic：

你正在使用原始的收藏，这是不好的，我sugest调整你的代码类似于：

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);