使用 PriorityQueue (Java) 进行字符串排序的问题

Question

我试图使用 PriorityQueue 对字符串列表进行排序并删除重复项。最初我使用 PriorityQueue，它不会改变顺序。我改成 TreeSet 后，就成功了。但是，我想了解定义了比较器的优先级队列有什么问题。很想听听一些解释。

无效代码：

public class RemoveDuplicateStrings {
    public static ArrayList<String> removeDuplicates(List<String> input) {
        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> a.compareTo(b));

        for (String s : input) {
            if (!pq.contains(s)) {
                pq.add(s);
            }
        }
        return new ArrayList<String>(pq);
    }

    public static void main(String[] args) {
        List<String> output = removeDuplicates(List.of("Hey", "Hi", "Hello", "Hey", "Hello"));
        System.out.println(output);
    }
}

我得到的结果： [Hello, Hi, Hey]，正确的顺序应该是：你好，嘿，嗨。

在我将数据结构更改为具有相同比较器的TreeSet 后，它起作用了。

Answer 1

您正在使用 ArrayList constructor that copies elements from the collection that is passed as an argument, and invokes toArray method on it. For PriorityQueue it just makes the copy of the underlying array and those elements are in no particular order. From the PriorityQueue::toArray 文档 :

Returns an array containing all of the elements in this queue. The elements are in no particular order.

但是对于 TreeSet::toArray（继承自 AbstractCollection 的实现）：

Returns an array containing all of the elements in this collection. If this collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order

实际上 TreeSet 保证了由它的迭代器编辑的元素的顺序 return。来自 TreeSet::iterator 文档：

Returns an iterator over the elements in this set in ascending order.

这就是为什么你会得到这样的结果。要得到你想要的东西，你必须轮询你的队列以按照比较器定义的顺序接收元素：

public static ArrayList<String> removeDuplicates(List<String> input) {
        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> a.compareTo(b));

        for (String s : input) {
            if (!pq.contains(s)) {
                pq.add(s);
            }
        }

        ArrayList<String> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll());
        }
        return result;
}

这里的关键是 PriorityQueue 的迭代器没有按特定顺序 return 元素，但是对于 TreeSet 顺序是升序的（考虑到比较器）。

使用 PriorityQueue (Java) 进行字符串排序的问题

Issues of String sort with PriorityQueue (Java)

java

sorting

priority-queue

comparator