带有内部比较器的 PriorityQueue class

Question

我尝试用递减顺序的内部比较器 class 实现优先级队列，但是当我打印优先级队列时，我没有得到正确的结果。当我尝试使用 Collection.sort 的相同比较器代码来实现列表排序时（具有相同的值）。我得到了正确的结果。能解释一下吗？

//int[] nums = {50,10, 20, 30, 40};
    public static void TestComparatorcomparemethod(int[] nums){
        PriorityQueue<Integer> pq= new PriorityQueue<>(nums.length,new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                int a = (int)o1;
                int b = (int)o2;
                if (a > b)
                    return -1;
                else if (a==b)
                    return 0;
                else
                    return 1;
            }
        });
        for (int node:nums){
            pq.add(node);}
        System.out.println("pq values are " + pq);
}

以上代码的答案是 pq 值为 [50, 40, 20, 10, 30]

        List<Integer> al = new ArrayList<>();
        al.add(50);
        al.add(10);
        al.add(20);
        al.add(30);
        al.add(40);
        Collections.sort(al, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                int a = (int)o1;
                int b = (int)o2;
                if (a > b)
                    return -1;
                else if (a==b)
                    return 0;
                else
                    return 1;
            }
        } );
        System.out.println("The arraylist values are: " + al);

以上代码的答案是数组值为：[50, 40, 30, 20, 10]

Answer 1

对于意外顺序 [50, 40, 20, 10, 30] 没问题（预期）的优先级队列。因为迭代优先级队列不保证排序顺序。但是，如果您使用 peek/poll，您将看到返回了预期值。

来自DOCUMENTATION：

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

您的比较器代码没问题。如果您确实需要按顺序打印值，请尝试：

 System.out.println("pq values are " + Arrays.sort(pq.toArray());

Answer 2

当您打印优先级队列元素时：

System.out.println("The arraylist values are: " + al);

不保证将要打印的元素顺序进行排序。这可能是因为优先级队列是使用某种堆数据结构实现的，以实现高效的最小元素查找和插入。因此，当您使用上述代码打印元素时，您将打印堆中未排序的元素。

这并不意味着您的优先级队列不工作。

遍历优先级队列中元素最有效的正确方式是使用poll()函数，例如：

pq_elem = pq.poll()
while(pq_elem != Null){
  System.out.println(pq_elem)
  pq_elem.poll()
}

带有内部比较器的 PriorityQueue class

PriorityQueue with inner comparator class

java

priority-queue

comparator