Изменение Java PriorityQueue до Max PQ

Приоритетная реализация Queue в стандартной библиотеке Java представляется мини-приоритетной очередью, которую я нашел несколько запутанной. Чтобы превратить его в макс, я создал собственный объект компаратора.

Comparator<Integer> cmp = new Comparator<Integer>()
{
    public int compare( Integer x, Integer y )
    {
        return y - x;
    }
};

Мне было интересно, было ли более элегантное решение. По сути, я не являюсь общей очередью приоритетов, которую можно использовать для реализации Dijkstras и т.д. Я даже не понял, что будут те, которые работают в обратном порядке:/

Ответы

Ответ 2

Вот фрагмент кода, использующий Collections.reverseOrder() -

    PriorityQueue<Integer> maxPQ = new PriorityQueue<Integer>(20,Collections.reverseOrder());

Вам также необходимо предоставить начальную емкость очереди приоритетов (здесь 20) вместе с компаратором.

Ответ 3

Не уверен, что вы подразумеваете под элегантным, но когда я хочу, чтобы PQ реализовывался как MaxHeap (используется в Dijkstra), я просто использую встроенный конструктор компаратора.

PriorityQueue<Integer> PQ= new PriorityQueue<Integer>(20, new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });

Это достаточно просто для любого времени, когда я ищу что-то простое и хочу только один раз использовать Comparator.

Ответ 4

Если у вас есть существующий компаратор, вы можете создать общий конверсионный компаратор.

public class InverseComparator<T> implements Comparator<T> {
    private final Comparator<T> delegate;

    public InverseComparator(Comparator<T> delegate) {
        this.delegate = delegate;
    }

    public int compare(T x, T y) {
        return delegate(y, x);
    }
}