Java：从优先级队列中得出奇怪的队列顺序

叶国兴

2023-03-14

问题内容：

我编写了一个迷宫求解程序，该程序应该支持DFS，BFS，A
*，Dijkstra和贪婪算法。无论如何，我选择了PriorityQueue作为我的边界数据结构，因为我认为优先级的行为就像队列，堆栈或优先级队列一样，取决于比较器的实现。

这是我实现比较器以将优先级队列转换为队列的方式：

/
由于优先级队列的“自然排序”元素最少，并且常规比较器在第一个小于第二个时返回-1，因此被黑的比较器始终返回1，因此当前（最后一个）平方为放在尾部（这应该递归工作）
/

public int compare(Square square1, Square square2)
{
    return 1;
}

但是，在进行BFS之后，迷宫的解决方案并不是最佳的。

迷宫从坐标（35,1）的右上角开始，我的程序检查左，然后上，然后下，然后是右邻居。这是我做的println：

选出（35,1）

添加（34,1）

添加（35,2）

选出（34,1）

添加（33,1）

添加（34,2）

选出（35,2）

添加（35,3）

选出（33,1）

添加（32,1）

添加（33,2）

轮询（34,2）

加（34,3）

轮询（32,1）

......

BFS（35,3）中的通知应在（32,1）之前被轮询，因为前者在后者之前被添加到队列中。真正令我感到困惑的是，数据结构的行为就像一个队列-
所有新成员都是从后面添加的-直到我添加（32,1），它被放置在队列的开头。

我认为我的比较器应该强制优先级队列将新来者排在后面。对我来说甚至更奇怪的是，数据结构将其性质从队列更改为中间的堆栈。

非常感谢你们前面的家伙，并为我的英语不好对不起，肖恩

问题答案：

您实现的方法compare是错误的，并且仅当您以假定的非常特定的方式调用它时才有效。但是，您不知道PriorityQueue实际调用什么上下文compare。compare可以在数据结构内部的现有元素上调用该函数，而不是在新元素上调用，反之亦然。

（即使您确实阅读了源代码并对其进行了跟踪并发现该特定实现以某种方式起作用，如果您希望代码可维护，也不应依赖于此。至少，您应该使自己成为可维护的。必须解释其工作原理，以完成更多工作。）

您可以使用某种计数器并将其分配为每个添加项的值，然后compare根据该值正确实现。

正确的实现compare可能如下所示：

int compare(Object x, Object y){
    return x.getSomeProperty() - y.getSomeProperty();
}

请注意，如果切换参数的顺序，答案也将改变。不，返回INT并没有
一定要来自{-1，0，1}。规格要求为0，或者是负数或正数。您可以使用任意一个，只要它是正确的符号即可。