Java: странный порядок очереди из приоритетной очереди

Question

Я написал программу решения лабиринтов, которая должна поддерживать DFS, BFS, A*, Dijkstra и жадный алгоритм. В любом случае я выбрал PriorityQueue для своей пограничной структуры данных, поскольку я думал, что приоритет может вести себя как очередь, стек или очередь приоритетов, в зависимости от реализации компаратора.

Вот как я реализовал свой компаратор, чтобы превратить очередь с приоритетами в очередь:

/Поскольку "естественное упорядочение" очереди с приоритетами имеет наименьший элемент в голове, и обычный компаратор возвращает -1, когда первый меньше второго, взломанный компаратор всегда возвращает 1, так что текущий (последний) квадрат будет помещается в хвост (это должно работать рекурсивно)/

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

Однако мое решение для лабиринта не было оптимальным после того, как я сделал BFS.

Лабиринт начинается в верхнем правом углу с координатой (35,1), и моя программа проверяет левое, затем вверх, затем вниз, затем правый сосед. Вот печать, которую я сделал:

опрошены (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), который был помещен в начало очереди.

Я думал, что мой компаратор должен заставить приоритетную очередь помещать новичков в спину. Что еще более странно для меня, так это то, что структура данных изменила свою природу с очереди на стек в середине.

Большое спасибо вам, ребята, извините за мой плохой английский, С уважением, Шон

Answer 1

То, как вы реализовали compare неверно, и будет работать, только если он вызывается только очень специфическим образом, который вы предполагаете. Однако вы не знаете, в каком контексте PriorityQueue на самом деле звонки compare, compare Функция вполне может быть вызвана для существующего элемента в структуре данных, а не для нового, или наоборот.

(Даже если вы прочитали исходный код, отследили его и обнаружили, что эта конкретная реализация работает определенным образом, вы не должны зависеть от этого, если хотите, чтобы ваш код был поддерживаемым. По крайней мере, вы бы сами создавали больше работы, объясняя, почему это работает.)

Вы можете просто использовать какой-то счетчик и назначить его в качестве значения для каждого добавленного элемента, а затем реализовать compare правильно на основе значения.

Правильная реализация compare может выглядеть так:

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

Обратите внимание, что если вы измените порядок параметров, ответ также изменится. Нет, возвращаемое int не обязательно должно быть из {-1, 0, 1}. Спецификация требует 0, или отрицательное или положительное целое число. Вы можете использовать любой, какой пожелаете, при условии, что это правильный знак.