在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()); 
    }