Java优先队列应该如何工作？

Question

简单来说，我正在实现一个图表并且现在正在处理Kruskal算法，我需要一个优先队列。 我对优先队列的定义是具有最小关键字的元素应该首先出现？ 这个定义是否错误？ 因为当我将带权边（或数字）插入队列时，它们没有被排序。

PriorityQueue<Integer> tja = new PriorityQueue<Integer>(); 
tja.add(55);
tja.add(99); 
tja.add(1); 
tja.add(102);
tja.add(54);
tja.add(51);
System.out.println(tja);

那将输出这个; [1, 54, 51, 102, 99, 55]。这不是我想要的排序方式！是的，我制作了一个比较器，它进入优先级队列，从边缘对象中提取数字并基于该整数进行比较。所以这应该可以工作，或者我完全误解了这种数据结构的概念？

- Algific

---

为了获得排序的布局，您应该使用以下代码：while (!tja.isEmpty()){ System.out.println(tja.poll()); } - serhii

Answer 1

System.out.println调用了toString()方法，该方法使用迭代器，但不能保证迭代器遵循自然顺序。根据文档中的描述：“在iterator()方法中提供的迭代器不能保证以任何特定顺序遍历优先级队列中的元素。”

- omerkudat

---

那么，有没有可能打印优先队列？ - Ahmed Hamdy

没关系，没有办法...如果你让我知道，我会更新答案。 - Ahmed Hamdy

Answer 2

我对Java中的PriorityQueue没有经验，但看起来优先级并未集成到iterator()或toString()（使用iterator()）中。

如果你这样做：

    while (tja.size()>0)
        System.out.println(tja.remove());

你可以获得正确的结果。

- Grzegorz Oledzki

---

完美，因此结构在运行删除之前未被正确排序。 - Algific

不，结构总是正确排序的，只是在迭代时不是。但是如果您调用poll()、peek()或remove()，您会按正确顺序获取元素。 - omerkudat

@data_hepp 不是的。Remove不会对结构进行排序。结构已经排序，但是它内部使用的toString()或iterator()不能保证按顺序遍历。 - Varun

Answer 3

如果您不了解二叉堆的工作原理，请先了解最小堆和最大堆结构。PriorityQueue基于堆实现，但并不按升序对项进行排序，而是对其进行堆排序。

请查看链接：优先队列 您得到的输出是正确的。

- Dixit Gokhale