Приоритетная Очередь Java с пользовательским анонимным компаратором
Простите мне, если это - испытанный вопрос, но я испытываю немного затруднений при понимании этого.
У меня в настоящее время есть класс Узел, и каждый 'узел' является квадратом в лабиринте. Я пытаюсь реализовать* алгоритм, таким образом, каждый из этих узлов будет иметь f-стоимость (интервал) элемент данных в нем. Я задавался вопросом, существует ли способ, которым я могу создать приоритетную очередь этих узлов и настроить переменную f-стоимости как компаратор?
Я посмотрел на примеры онлайн, но все, что я могу найти, является Строковыми приоритетными очередями. Я могу реализовать Компаратор для класса Узла? Это позволило бы мне получать доступ к элементу данных, сохраненному в нем?
Большое спасибо!
4 ответа
Absolutely.
Вы можете использовать PriorityQueue на основе анонимного Comparator, переданного в конструктор:
int initCapacity = 10;
PriorityQueue<Node> pq = new PriorityQueue<Node>(initCapacity, new Comparator<Node>() {
public int compare(Node n1, Node n2) {
// compare n1 and n2
}
});
// use pq as you would use any PriorityQueue
Если ваш класс Node уже реализует Comparable, вам даже не нужно определять новый Comparator, поскольку этот порядок будет использоваться по умолчанию. При отсутствии любого другого метода будет использоваться естественное упорядочивание между объектами.
В java.util есть класс PriorityQueue. Вы можете использовать это, и он будет использовать либо естественный порядок (Node реализует Comparable), либо компаратор, предоставленный в конструкторе (если вы не хотите, чтобы этот код был внутри вашего класса Node). Любой класс может получить доступ к любым данным внутри другого, если вы это разрешите, сделав поле неприкосновенным (потенциально плохой стиль ООП) или предоставив метод доступа public int getG (), public int getH (), public int getF () .
public class Node implements Comparable<Node>{
public int compareTo(Node o) {
// your comparative function
return 0;
}
}
если compareTo возвращает отрицательное целое число, это означает «меньше», 0 означает «равно», 1 означает «больше»
, что одна функция - это все, что вам нужно для использования PriorityQueue.
РЕДАКТИРОВАТЬ: сравнение - это другой способ, я напортачил. -1 <| 0 = | 1> Я уже почему-то читаю их справа налево.
Из Javadocs:
Беспредельная очередь приоритетов, основанная на куче приоритетов. Эта очередь упорядочивает элементы в соответствии с порядком заданному во время построения, который задается либо в соответствии с их естественному порядку (см. Сравнимый), либо в соответствии с компаратором
Более того, приоритетные очереди поддерживают общие типы данных. Поэтому, если вы реализуете Comparable в своем классе Node, то вы можете создать PriorityQueue и использовать его нормально.
В качестве альтернативы существует конструктор PriorityQueue(int initialCapacity, Comparator comparator), который принимает Comparator как часть конструктора PriorityQueue. Если вы предпочитаете этот метод, вашему классу узла не нужно содержать дополнительный код, необходимый при наследовании Comparable.