Java 8中LinkedList接收PriorityQueue后无法保证元素顺序的问题

核心原因：PriorityQueue的迭代顺序并非排序顺序 #

Java的PriorityQueue是基于堆结构实现的优先级队列，它仅保证每次通过poll()/peek()取出的元素是优先级最高的，但它的迭代器遍历顺序并不是严格排序后的顺序。堆的底层存储结构（通常是数组）是为了维护堆的性质设计的，并非按排序后的顺序排列。

你的代码中，new LinkedList<>(firstQue)会调用LinkedList的addAll方法，该方法会遍历传入集合（此处为PriorityQueue）的迭代器来逐个添加元素，因此得到的LinkedList元素顺序就是PriorityQueue迭代器的遍历顺序，而非你预期的排序后的顺序。

正确的实现方式 #

如果需要得到一个按PriorityQueue优先级排序后的LinkedList，有两种常用方式：

方式1：通过poll()逐个取出元素 #

利用PriorityQueue的poll()方法每次取出优先级最高的元素，依次添加到LinkedList中：

PriorityQueue<Place> firstQue = new PriorityQueue<>(Comparator.comparingInt(o -> o.v));
// 添加数据到firstQue

Queue<Place> que = new LinkedList<>();
Place place;
while ((place = firstQue.poll()) != null) {
    que.add(place);
}

注意：这种方式会清空原PriorityQueue，若需保留原队列，可先复制一份再操作。

方式2：使用Stream排序后收集到LinkedList #

借助Stream API，用和PriorityQueue一致的Comparator对元素排序后收集：

PriorityQueue<Place> firstQue = new PriorityQueue<>(Comparator.comparingInt(o -> o.v));
// 添加数据到firstQue

Queue<Place> que = firstQue.stream()
                           .sorted(Comparator.comparingInt(o -> o.v))
                           .collect(Collectors.toCollection(LinkedList::new));

这种方式不会修改原PriorityQueue，适合需要保留原队列的场景。

内容的提问来源于stack exchange，提问作者suw0n