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

125

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

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

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

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

Борут Флис
источник
5
Я думаю, вам следует использовать конструктор, который получает для этого компаратор. Используйте Collections.reverseOrder, чтобы получить обратный компаратор.
Эдвин Далорцо
1
нужно сдать компаратор. см. stackoverflow.com/questions/683041/…
DarthVader
Это может помочь: tech693.blogspot.com/2018/09/…
Java Guru

Ответы:

233

Как насчет этого:

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);
}

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

Эдвин Далорцо
источник
14
Collections.reverseOrder()также перегружен для использования компаратора, поэтому он также работает, если вы сравниваете пользовательские объекты.
flying Sheep
14
В Java 8 PriorityQueue есть новый конструктор, который просто принимает компаратор в качестве аргумента PriorityQueue(Comparator<? super E> comparator).
abhisheknirmal
75

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

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

// There is overflow problem when using simple lambda as comparator, as pointed out by Фима Гирин.
// PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);

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

pq.add(10);
pq.add(5);
System.out.println(pq.peek());

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

Гуантун Шен
источник
лямбда-функция называет свои входные параметры x и y и возвращает yx, что в основном и делает класс компаратора int, за исключением того, что он возвращает xy
Эди Байс,
15
Компаратор вроде (x, y) -> y - xможет не подходить для длинных целых чисел из-за переполнения. Например, числа y = Integer.MIN_VALUE и x = 5 дают положительное число. Лучше использовать new PriorityQueue<>((x, y) -> Integer.compare(y, x)). Хотя, @Edwin Dalorzo предлагает лучшее решение Collections.reverseOrder().
Фима Гирин
1
@ ФимаГирин Это правда. -2147483648 - 1 становится 2147483647
Guangtong Shen
27

Вы можете предоставить настраиваемый 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;
    }
});

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

Надеюсь это поможет!

templatetypedef
источник
5
возможно, для максимального приоритета q lhs <rhs возвращает +1; то, что вы здесь написали, является минимальным q после моего тестирования
sivi
Для обратной печати, то есть если самые высокие элементы должны быть напечатаны первыми в очереди с приоритетом, это должно бытьif (rhs < lhs) return +1; if (rhs > lhs) return -1;
Тиа
@Diksha Я считаю, что код, который у меня есть, эквивалентен тому, что вы публикуете. Я просто использовал отношение больше, чем меньше.
templatetypedef
4
на самом деле, моя ошибка .. Я имел в виду, что это должно быть так:if (lhs < rhs) return +1; if (lhs > rhs) return -1;
Тиа
1
@ShrikantPrabhu Хороший улов - теперь это исправлено!
templatetypedef
14
PriorityQueue<Integer> pq = new PriorityQueue<Integer> (
  new Comparator<Integer> () {
    public int compare(Integer a, Integer b) {
       return b - a;
    }
  }
);
Варун Джунджа
источник
В чем проблема ?
CMedina
Это идеально и делает именно то, о чем просили, превращая минимальную кучу в максимальную.
Kamran
2
использование b-aможет вызвать, overflowпоэтому следует избегать его использования и использовать Collections.reverseOrder();в качестве компаратора или заменить ba, на Integer.compare(a,b);которое было добавленоJava 8
Yug Singh
10

В Java 8+ вы можете создать очередь с максимальным приоритетом одним из следующих методов:

Способ 1:

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

Способ 2:

PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b - a); 

Способ 3:

PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b.compareTo(a)); 
Apadana
источник
8

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

Компаратор должен переопределить метод сравнения.

int compare(T o1, T o2)

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

По умолчанию PriorityQueue, предоставляемый 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 ()

Рохан
источник
4

Вот пример 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

Nobal
источник
4

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

PriorityQueue<Integer> maxPriorityQ = new PriorityQueue<Integer>(Collections.reverseOrder());
Аншу Шекхар
источник
3

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

Хтонический проект
источник
3

Измените PriorityQueue на MAX PriorityQueue Метод 1: очередь pq = new PriorityQueue <> (Collections.reverseOrder ()); Метод 2: очередь pq1 = new PriorityQueue <> ((a, b) -> b - a); Давайте посмотрим на несколько примеров:

public class Example1 {
    public static void main(String[] args) {

        List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.addAll(ints);
        System.out.println("Priority Queue => " + pq);
        System.out.println("Max element in the list => " + pq.peek());
        System.out.println("......................");
        // another way
        Queue<Integer> pq1 = new PriorityQueue<>((a, b) -> b - a);
        pq1.addAll(ints);
        System.out.println("Priority Queue => " + pq1);
        System.out.println("Max element in the list => " + pq1.peek());
        /* OUTPUT
          Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
          Max element in the list => 888
          ......................
           Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
           Max element in the list => 888

         */


    }
}

Возьмем известную проблему интервью: K-й самый большой элемент в массиве с использованием PriorityQueue

public class KthLargestElement_1{
    public static void main(String[] args) {

        List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
        int k = 3;
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.addAll(ints);
        System.out.println("Priority Queue => " + pq);
        System.out.println("Max element in the list => " + pq.peek());
        while (--k > 0) {
            pq.poll();
        } // while
        System.out.println("Third largest => " + pq.peek());
/*
 Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
Max element in the list => 888
Third largest => 666

 */
    }
}

По-другому :

public class KthLargestElement_2 {
    public static void main(String[] args) {
        List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
        int k = 3;

        Queue<Integer> pq1 = new PriorityQueue<>((a, b) -> b - a);
        pq1.addAll(ints);
        System.out.println("Priority Queue => " + pq1);
        System.out.println("Max element in the list => " + pq1.peek());
        while (--k > 0) {
            pq1.poll();
        } // while
        System.out.println("Third largest => " + pq1.peek());
        /*
          Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222] 
          Max element in the list => 888 
          Third largest => 666

         */
    }
}

Как мы видим, оба дают одинаковый результат.

Судипта Дутта
источник
3

Этого можно добиться, используя

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
Ajinkya_M
источник
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;
    }
});
SiVi
источник
Для обратной печати, то есть если элементы с наивысшим уровнем должны быть напечатаны первыми в очереди с приоритетом, это должно быть if (rhs < lhs) return +1;if (rhs> lhs) return -1;
Tia
Вы можете отредактировать его, если хотите. У меня нет времени подтверждать то, что вы написали. В моей настройке то, что я написал, было правильным
sivi
1

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

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

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

Хория Коман
источник
1
PriorityQueue<Integer> lowers = new PriorityQueue<>((o1, o2) -> -1 * o1.compareTo(o2));
Сумит Кумар Саха
источник
0

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

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

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

striker28
источник
0

Мы можем сделать это, создав наш класс CustomComparator , реализующий интерфейс Comparator, и переопределив его метод сравнения. Ниже приведен код того же:

import java.util.PriorityQueue;
import java.util.Comparator;
public class Main
{
    public static void main(String[] args) {
        PriorityQueue<Integer> nums = new PriorityQueue<>(new CustomComparator());
        nums.offer(21);
        nums.offer(1);
        nums.offer(8);
        nums.offer(2);
        nums.offer(-4);
        System.out.println(nums.peek());
    }
}
class CustomComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer n1, Integer n2){
        int val = n1.compareTo(n2);
        if(val > 0)
           return -1;
        else if(val < 0)
            return 1;
        else
            return 0;
    }
}
Хардик Вагадиа
источник