將值添加到優先級隊列時，何時對值進行排序？

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