5

简短的故事，我正在实现一个图表，现​​在我正在研究 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]。这不像我想要的那样排序！是的，我做了一个比较器，它进入优先级队列，从边缘对象中提取数字并基于该 int 进行比较。所以这应该有效，还是我完全误解了这个数据结构如何工作的整个概念？

4

3 回答 3

17

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

于 2009-11-25T09:02:19.990 回答
7

我没有使用PriorityQueueJava 的经验，但看起来优先级的东西没有集成到iterator()or toString()（使用iterator()）。

如果你这样做：

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

你会得到正确的结果。

于 2009-11-25T09:00:46.090 回答
1

您熟悉二进制堆的功能吗？如果不是，请检查最小堆和最大堆结构。PriorityQueue 在堆上实现。PriorityQueue 不会按升序对项目进行排序，但会对其进行堆排序。

通过链接：优先队列

你得到的输出是正确的。

于 2015-03-18T11:30:03.237 回答