java - java中使用优先级队列对元素进行排序

Question

我想使用 Java 中的优先级队列对元素进行排序。

这是我的代码。有什么问题吗？

import java.io.*;
import java.util.*;

class PQ {
    static class IntCompare implements Comparator<Integer>{
        @Override
        public int compare(Integer arg0, Integer arg1) {
            if(arg0 > arg1)
                return -1;
            else if(arg0 < arg1)
                return 1;
            else
                return 0;
        }
   }

    public static void main (String[] args) {
        int a[] = { 1, 3, 8, 5, 2, 6 };

        Comparator<Integer> c = new IntCompare();
        PriorityQueue<Integer> pq=new PriorityQueue<>(c);

        for(int i = 0; i < a.length; i++)
            pq.add(a[i]);

        System.out.println(pq);
    }
}

我的输出是:

8, 5, 6, 1, 2, 3

正确的输出:

8, 6, 5, 3, 2, 1

Answer 1

当您调用System.out.println(pq)时，会隐式调用toString方法。

toString PriorityQueue 方法扩展自 AbstractCollection，其中

Returns a string representation of this collection. The string representation consists of a list of the collection's elements in the order they are returned by its iterator, enclosed in square brackets ("[]").

而iterator PriorityQueue 不保证按特定顺序遍历:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.

因为队列基于 heap .

您可以逐一轮询元素以获得有序元素:

while (pq.size() != 0) {
    System.out.print(pq.poll() + ","); // 8,6,5,3,2,1,
}