在Java中使用PriorityQueue與任何比較器

Question

常見問題：如何使用自定義類的不同比較器對PriorityQueue中的對象進行排序？

我試過用在適當的對與預期類似的排序結果在接下來的代碼中的對象的priorityqueues和列表的這個比較要做到：

class User{ 
    private Integer id; 
    private String name; 
    public User(Integer i, String n){ 
    this.id=i; 
    this.name=n; 
    } 
    public Integer getId() {return id;} 
    public String getName() {return name;} 
    @Override 
    public boolean equals(Object obj) { 
    if (this == obj)return true; 
    if (obj == null)return false; 
    if (getClass() != obj.getClass())return false; 
    User other = (User) obj; 
    if(id == null){ 
     if (other.id != null)return false; 
    }else if(!id.equals(other.id))return false; 
    return true; 
    } 
    @Override 
    public String toString() {return "[id:" + id + ", name:" + name + "]";} 
} 

public class MyPriorityQueue { 

    public static Comparator<User> cmpId = Comparator.comparingInt(x -> x.getId()); 
    public static Comparator<User> cmpNameLength = Comparator.comparingInt(x -> x.getName().length()); 

    public static void main(String[] args) { 
    List<User> users = new ArrayList<User>(10); 
    users.add(new User(1,"11111")); 
    users.add(new User(3,"333")); 
    users.add(new User(5,"5")); 
    users.add(new User(4,"44")); 
    users.add(new User(2,"2222")); 

    Queue<User> ids = new PriorityQueue<User>(10, cmpId); //use first comparator 
    users.forEach(x-> ids.offer(x)); 

    Queue<User> names = new PriorityQueue<User>(10, cmpNameLength); //use second comparator 
    names.addAll(users); 

    System.out.println("Variant_1.1:"); 
    ids.forEach(System.out::println); 

    System.out.println("Variant_2.1:"); 
    names.forEach(System.out::println); 

    System.out.println("Variant_1.2:"); 
    users.sort(cmpId); //use first comparator 
    users.forEach(System.out::println); 

    System.out.println("Variant_2.2:"); 
    users.sort(cmpNameLength); //use second comparator 
    users.forEach(System.out::println); 
    } 
} 

輸出：

Variant_1.1: //Failed sorted queue by user.id with using comporator cmpId 
    [id:1, name:11111] 
    [id:2, name:2222] 
    [id:5, name:5] 
    [id:4, name:44] 
    [id:3, name:333] 
Variant_2.1: //Failed sorted queue by length of the user.name with cmpNameLength 
    [id:5, name:5] 
    [id:4, name:44] 
    [id:3, name:333] 
    [id:1, name:11111] 
    [id:2, name:2222] 
Variant_1.2: // OK: correctly sorted list by user.id with cmpId comporator 
    [id:1, name:11111] 
    [id:2, name:2222] 
    [id:3, name:333] 
    [id:4, name:44] 
    [id:5, name:5] 
Variant_2.2: //OK: for list by length of the user.name with cmpNameLength 
    [id:5, name:5] 
    [id:4, name:44] 
    [id:3, name:333] 
    [id:2, name:2222] 
    [id:1, name:11111] 

我的預期即：

• 變體1.1和2.1的結果;
• 變體1.2和2.2的結果;

將是相同的，但它們是不同的。

我的問題：我爲排序priorytyqueue /比較器做了什麼錯誤，以及如何獲得排序結果的優先隊列作爲我的例子中的適當列表？

Answer 1

在您的代碼示例中，您使用Iterable#forEach來遍歷隊列。

ids.forEach(System.out::println); 

names.forEach(System.out::println); 

forEach最終代表到Iterable#iterator。但是，需要注意的是，PriorityQueue#iterator中的子類重寫具有不同的JavaDoc，並且有關於排序的特別說明。

返回此隊列中元素的迭代器。迭代器不會以任何特定順序返回元素。

換句話說，不能保證迭代PriorityQueue將使用您的Comparator。如果您通過反覆調用PriorityQueue#poll來更改自己的代碼以排除隊列，那麼我希望您會看到根據您的自定義Comparator排序的結果。

挖掘OpenJDK源代碼，我們可以看到PriorityQueue內部的數據結構是binary heap。這由一個數組支持，當調用者添加和移除隊列的元素時，代碼在內部保持堆不變。

/** 
* Priority queue represented as a balanced binary heap: the two 
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The 
* priority queue is ordered by comparator, or by the elements' 
* natural ordering, if comparator is null: For each node n in the 
* heap and each descendant d of n, n <= d. The element with the 
* lowest value is in queue[0], assuming the queue is nonempty. 
*/ 
transient Object[] queue; // non-private to simplify nested class access 

然而，內部Iterator實現只使用整數光標通過陣列向前掃描，而不考慮元件的優先級或堆的佈局。

  return (E) queue[lastRet = cursor++]; 

Answer 2

你沒有做錯什麼，它只是PriorityQueue的迭代器是：

不能保證遍歷優先級隊列中的元素在任何特定的順序（Javadoc）

forEach方法內部使用迭代器，所以存在相同的問題。

這是因爲底層的數據結構是這樣的，它可以在您對項目進行排序時「排序」。如果實現者想要按照排序順序返回項目，他們必須首先收集項目，然後在返回之前對其進行分類。這會導致性能下降，所以（我認爲）決定將它無序地返回，因爲PriorityQueue主要是一個隊列，而不是一個已排序的集合，並且用戶總是可以自己排序該項目（這與其獲得的效率一樣高效）。

爲了獲得訂購的元素，這樣做：

while(pq.peek() != null){ 
     System.out.println(pq.poll()); 
    }