Изменить priorityQueue на max priorityqueue

у меня есть приоритетная очередь в Java целых чисел:

 PriorityQueue<Integer> pq= new PriorityQueue<Integer>();

когда я называю pq.poll() Я получаю минимальный элемент.

вопрос: как изменить код, чтобы получить максимальный элемент?

11 72
javascript scala-collections priority-queue

11 ответов:

как насчет такой:

PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());
queue.offer(1);
queue.offer(2);
queue.offer(3);
//...

Integer val = null;
while( (val = queue.poll()) != null) {
    System.out.println(val);
}

The Collections.reverseOrder() предоставляет Comparator что бы отсортировать элементы в PriorityQueue в порядке oposite к их естественному порядку в этом случае.

153

вы можете использовать лямбда-выражение с Java 8.

следующий код будет печатать 10, больше.

PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
pq.add(10);
pq.add(5);
System.out.println(pq.peek());

лямбда-функция принимает два целых числа в качестве входных параметров, вычитает их друг из друга и возвращает арифметический результат. Лямбда-функция реализует функциональный интерфейс,Comparator<T>. (Это используется на месте, в отличие от анонимного класса или дискретной реализации.)

36

Вы можете предоставить собственный Comparator объект, который ранжирует элементы в обратном порядке:

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(defaultSize, new Comparator<Integer>() {
    public int compare(Integer lhs, Integer rhs) {
        if (lhs < rhs) return +1;
        if (lhs.equals(rhs)) return 0;
        return -1;
    }
});

теперь очередь приоритетов отменит все свои сравнения, поэтому вы получите максимальный элемент, а не минимальный элемент.

надеюсь, что это помогает!

19
PriorityQueue<Integer> pq = new PriorityQueue<Integer> (
  new Comparator<Integer> () {
    public int compare(Integer a, Integer b) {
       return b - a;
    }
  }
);
9

элементы приоритетной очереди упорядочиваются в соответствии с их естественным порядком или компаратором, предоставленным во время построения очереди.

компаратор должен переопределить метод Compare.

int compare(T o1, T o2)

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

приоритетный запрос по умолчанию, предоставляемый Java, - это Min-Heap, Если вам нужна максимальная куча ниже приведен код

public class Sample {
    public static void main(String[] args) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() {

            public int compare(Integer lhs, Integer rhs) {
                if(lhs<rhs) return +1;
                if(lhs>rhs) return -1;
                return 0;
            }
        });
        q.add(13);
        q.add(4);q.add(14);q.add(-4);q.add(1);
        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }

}

Ссылка :https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator()

7

вот пример Max-Heap в Java:

PriorityQueue<Integer> pq1= new PriorityQueue<Integer>(10, new Comparator<Integer>() {
public int compare(Integer x, Integer y) {
if (x < y) return 1;
if (x > y) return -1;
return 0;
}
});
pq1.add(5);
pq1.add(10);
pq1.add(-1);
System.out.println("Peek: "+pq1.peek());

выход будет 10

4

можно использовать MinMaxPriorityQueue (Это часть библиотеки гуавы): вот документация. Вместо poll() нужно позвонить pollLast() метод.

3

вы можете попробовать что-то вроде:

PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> -1 * Integer.compare(x, y));

который работает для любой другой базовой функции сравнения вы могли бы иметь.

1

Я только что запустил моделирование Монте-Карло на обоих компараторах на двойной сортировке кучи min max, и они оба пришли к одному и тому же результату:

Это максимальные компараторы, которые я использовал:

(A) коллекции встроенный компаратор

 PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(Collections.reverseOrder());

(B) пользовательский компаратор 

PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(new Comparator<Integer>() {
    int compare(Integer lhs, Integer rhs) {
        if (rhs > lhs) return +1;
        if (rhs < lhs) return -1;
        return 0;
    }
});
0

вы можете попробовать нажать элементы с обратным знаком. Например: чтобы добавить a=2 & b=5, а затем опрос b=5.

PriorityQueue<Integer>  pq = new PriorityQueue<>();
pq.add(-a);
pq.add(-b);
System.out.print(-pq.poll());

Как только вы опросите главу очереди, измените знак для вашего использования. Это будет печатать 5 (больше элементов). Может использоваться в наивных реализациях. Определенно не надежное исправление. Я не рекомендую этого делать.

0

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

PriorityQueue<Integer> maxPriorityQ = new PriorityQueue<Integer>(Collections.reverseOrder());
0