Java PriorityQueue字符串排序原理及正确遍历方法

PriorityQueue底层采用堆结构，其toString()方法展示的是底层数组的物理存储状态，而非逻辑上的优先级顺序。若需按字典序输出，必须通过poll()或remove()方法逐个取出最小元素。

首先明确几个核心要点：Java的PriorityQueue默认按照字符串的自然顺序（字典序）进行优先级排序，这是公认的——'mackerel' < 'salmon' < 'trout'是确定的。然而，许多人误以为直接打印System.out.println(q)就能看到排序结果。实际上，该方法调用的是PriorityQueue.toString()，返回的是堆数组的底层存储状态，通常呈现为层级遍历的布局，并非优先级排序后的视图。

下面通过一个具体示例说明：

PriorityQueue q = new PriorityQueue<>();
q.offer("salmon");
q.offer("trout");
q.offer("mackerel");
System.out.println(q); // 输出类似 [mackerel, trout, salmon] —— 这是堆结构的内部表示！

这个输出看起来有些混乱，但并非排序错误。它展示了最小堆典型的数组存储形式：索引0处是最小值，但后续元素并不保证全局有序。原因是堆是一棵完全二叉树，数组中的每个位置并非按优先级排列。唯一确定的是堆顶（索引0）是当前最小元素。

✅ 那么，如何正确验证排序结果？持续取出队首元素即可：

while (!q.isEmpty()) {
    System.out.println(q.poll()); // 或 q.remove()
}

输出才会严格按字典序升序排列：

mackerel
salmon
trout

⚠️ 以下是一些关键注意事项：

• PriorityQueue不提供有序遍历的接口。iterator()并不保证顺序，因此切勿依赖for-each循环或toArray()来获取排序结果——这可能导致意料之外的结果。
• 若需要一次性获取有序列表，可以先通过new ArrayList<>(q)提取所有元素，再调用Collections.sort()进行排序。但该方法效率不如逐个调用poll()，因为poll()时间复杂度为O(log n)，而排序为O(n log n)。
• 使用自定义比较器时需谨慎：必须符合Comparator的契约——自反性、对称性、传递性，缺一不可，否则堆操作的稳定性将受到影响，行为变得不可预测。

总而言之，PriorityQueue的“优先级”仅体现在peek()、poll()、remove()等核心操作上，与其字符串表示并无直接关联。理解堆存储的本质，是正确运用该数据结构的关键。否则，仅凭打印出的数组，可能会误以为排序功能出现了问题。