Как использовать PriorityQueue?

Как мне получить PriorityQueue для сортировки по тому, что я хочу, чтобы он сортировался?

Кроме того, существует ли разница между offer и add?

Ответы

Ответ 1

Используйте перегрузку конструктора, которая принимает Comparator<? super E> comparator Comparator<? super E> comparator и сравните компаратор, который сравнивает подходящим образом для вашего порядка сортировки. Если вы приведете пример того, как вы хотите сортировать, мы можем предоставить пример кода для реализации компаратора, если вы не уверены. (Это довольно просто, хотя.)

Как уже было сказано в другом месте: offer и add - это просто разные реализации метода интерфейса. В источнике JDK, который я получил, add offer звонков. Несмотря на то, что add и offer имеют потенциально различное поведение в целом из-за способности offer указывать, что значение не может быть добавлено из-за ограничений размера, это различие не имеет значения в PriorityQueue которая не ограничена.

Вот пример сортировки очереди по длине строки:

// Test.java
import java.util.Comparator;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        Comparator<String> comparator = new StringLengthComparator();
        PriorityQueue<String> queue = new PriorityQueue<String>(10, comparator);
        queue.add("short");
        queue.add("very long indeed");
        queue.add("medium");
        while (queue.size() != 0) {
            System.out.println(queue.remove());
        }
    }
}

// StringLengthComparator.java
import java.util.Comparator;

public class StringLengthComparator implements Comparator<String> {
    @Override
    public int compare(String x, String y) {
        // Assume neither string is null. Real code should
        // probably be more robust
        // You could also just return x.length() - y.length(),
        // which would be more efficient.
        if (x.length() < y.length()) {
            return -1;
        }
        if (x.length() > y.length()) {
            return 1;
        }
        return 0;
    }
}

Вот вывод:

короткая

Средняя

очень долго

Ответ 2

Решение Java 8

Мы можем использовать lambda expression или method reference представленные в Java 8. В случае, если в Приоритетной очереди хранятся некоторые значения String (с емкостью 5), мы можем предоставить встроенный компаратор (на основе длины String):

Использование лямбда-выражения

PriorityQueue<String> pq=
                    new PriorityQueue<String>(5,(a,b) -> a.length() - b.length());

Использование метода Reference

PriorityQueue<String> pq=
                new PriorityQueue<String>(5, Comparator.comparing(String::length));

Тогда мы можем использовать любой из них как:

public static void main(String[] args) {
        PriorityQueue<String> pq=
                new PriorityQueue<String>(5, (a,b) -> a.length() - b.length());
       // or pq = new PriorityQueue<String>(5, Comparator.comparing(String::length));
        pq.add("Apple");
        pq.add("PineApple");
        pq.add("Custard Apple");
        while (pq.size() != 0)
        {
            System.out.println(pq.remove());
        }
    }

Это напечатает:

Apple
PineApple
Custard Apple

Чтобы изменить порядок (чтобы изменить его в очередь с максимальным приоритетом), просто измените порядок в встроенном компараторе или используйте в reversed:

PriorityQueue<String> pq = new PriorityQueue<String>(5, 
                             Comparator.comparing(String::length).reversed());

Мы также можем использовать Collections.reverseOrder:

PriorityQueue<Integer> pqInt = new PriorityQueue<>(10, Collections.reverseOrder());
PriorityQueue<String> pq = new PriorityQueue<String>(5, 
                Collections.reverseOrder(Comparator.comparing(String::length))

Итак, мы видим, что Collections.reverseOrder перегружен, чтобы взять компаратор, который может быть полезен для пользовательских объектов. reversed фактически использует Collections.reverseOrder:

default Comparator<T> reversed() {
    return Collections.reverseOrder(this);
}

предложение() против добавления()

Согласно документу

Метод offer вставляет элемент, если это возможно, в противном случае возвращает false. Это отличается от метода Collection.add, который может не добавить элемент, только выбрасывая непроверенное исключение. Метод предложения предназначен для использования, когда сбой является нормальным, а не исключительным случаем, например, в очередях с фиксированной емкостью (или "ограниченной").

При использовании очереди с ограниченной емкостью, предложение(), как правило, предпочтительнее, чем add(), который может не вставить элемент, только вызвав исключение. И PriorityQueue - это очередь с неограниченным приоритетом, основанная на куче приоритетов.

Ответ 3

Просто отправьте соответствующий Comparator в конструктор 

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

Единственное различие между offer и add это интерфейс, к которому они принадлежат. offer принадлежит Queue<E>, тогда как add изначально отображается в Collection<E>. Кроме того, оба метода делают то же самое - вставьте указанный элемент в очередь приоритетов.

Ответ 4

из API очереди:

Метод предложения вставляет элемент, если это возможно, в противном случае возвращает false. Это отличается от метода Collection.add, который не может добавить элемент только путем исключения неконтролируемого исключения. Метод предложения предназначен для использования, когда отказ является обычным, а не исключительным случаем, например, в очереди с фиксированной пропускной способностью (или "ограниченным" ).

Ответ 5

нет, как объявить в javadoc:

public boolean add(E e) {
    return offer(e);
}

Ответ 6

Здесь мы можем определить определяемый пользователем компаратор:

Ниже код:

 import java.util.*;
 import java.util.Collections;
 import java.util.Comparator; 


 class Checker implements Comparator<String>
 {
    public int compare(String str1, String str2)
    {
        if (str1.length() < str2.length()) return -1;
        else                               return 1;
    }
 }


class Main
{  
   public static void main(String args[])
    {  
      PriorityQueue<String> queue=new PriorityQueue<String>(5, new Checker());  
      queue.add("india");  
      queue.add("bangladesh");  
      queue.add("pakistan");  

      while (queue.size() != 0)
      {
         System.out.printf("%s\n",queue.remove());
      }
   }  
}

Выход:

   india                                               
   pakistan                                         
   bangladesh

Разница между предложением и методами добавления: ссылка

Ответ 7

Просто для того, чтобы ответить на вопрос add() и offer() (так как на другой вопрос отлично ответил imo, а это может и не быть):

Согласно JavaDoc для интерфейса Queue: "Метод offer вставляет элемент, если это возможно, в противном случае возвращает false. Это отличается от метода Collection.add, который может не добавить элемент только путем генерирования непроверенного исключения. Метод offer предназначен для использовать, когда сбой является нормальным, а не исключительным случаем, например, в очередях с фиксированной (или "ограниченной") емкостью ".

Это означает, что если вы можете добавить элемент (который всегда должен иметь место в PriorityQueue), они работают точно так же. Но если вы не можете добавить элемент, offer() даст вам хороший и довольно false возврат, в то время как add() выдает неприятное непроверенное исключение, которое вам не нужно в вашем коде. Если неудача при добавлении означает, что код работает должным образом и/или это то, что вы обычно проверяете, используйте offer(). Если ошибка добавления означает, что что-то не работает, используйте add() и обработайте полученное исключение в соответствии со спецификациями интерфейса Collection.

Они оба реализованы таким образом, чтобы полностью заполнить контракт в интерфейсе очереди, в котором указано, что offer() терпит неудачу, возвращая false (метод предпочтителен в ограниченных по объему очередях), а также поддерживать контракт в интерфейсе Collection, который указывает add() всегда не удается выполнить с помощью бросить исключение.

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

Ответ 8

Я также задавался вопросом о заказе на печать. Рассмотрим этот случай, например:

Для очереди с приоритетом:

PriorityQueue<String> pq3 = new PriorityQueue<String>();

Этот код:

pq3.offer("a");
pq3.offer("A");

может печатать иначе, чем:

String[] sa = {"a", "A"}; 
for(String s : sa)   
   pq3.offer(s);

Я нашел ответ из обсуждения на другом форуме, где пользователь сказал: "методы offer()/add() только вставляют элемент в очередь. Если вы хотите предсказуемый порядок, вы должны использовать peek/poll, которые возвращают голову очереди."

Ответ 9

В качестве альтернативы использованию Comparator вы также можете использовать класс, который вы используете, в PriorityQueue Внесите Comparable (и соответственно переопределите метод compareTo).

Обратите внимание, что обычно лучше использовать Comparable вместо Comparator, если это упорядочение - это интуитивное упорядочение объекта - если, например, у вас есть прецедент для сортировки объектов Person по возрасту, это вероятно, лучше всего использовать Comparator вместо этого.

import java.lang.Comparable;
import java.util.PriorityQueue;

class Test
{
    public static void main(String[] args)
    {
        PriorityQueue<MyClass> queue = new PriorityQueue<MyClass>();
        queue.add(new MyClass(2, "short"));
        queue.add(new MyClass(2, "very long indeed"));
        queue.add(new MyClass(1, "medium"));
        queue.add(new MyClass(1, "very long indeed"));
        queue.add(new MyClass(2, "medium"));
        queue.add(new MyClass(1, "short"));
        while (queue.size() != 0)
            System.out.println(queue.remove());
    }
}

class MyClass implements Comparable<MyClass>
{
    int sortFirst;
    String sortByLength;

    public MyClass(int sortFirst, String sortByLength)
    {
        this.sortFirst = sortFirst;
        this.sortByLength = sortByLength;
    }

    @Override
    public int compareTo(MyClass other)
    {
        if (sortFirst != other.sortFirst)
            return Integer.compare(sortFirst, other.sortFirst);
        else
            return Integer.compare(sortByLength.length(), other.sortByLength.length());
    }

    public String toString()
    {
        return sortFirst + ", " + sortByLength;
    }
}

Вывод:

1, short
1, medium
1, very long indeed
2, short
2, medium
2, very long indeed

Ответ 10

Приоритетная очередь имеет некоторый приоритет, назначенный каждому элементу. Элемент с наивысшим приоритетом отображается в верхней части очереди. Теперь, зависит от вас, как вы хотите, чтобы приоритет присваивался каждому из элементов. Если вы этого не сделаете, Java сделает это по-умолчанию. Элементу с наименьшим значением присваивается наивысший приоритет и, следовательно, сначала удаляется из очереди. Если есть несколько элементов с одинаковым наивысшим приоритетом, связь нарушается произвольно. Вы также можете указать порядок с использованием Comparator в конструкторе PriorityQueue(initialCapacity, comparator)

Пример кода:

PriorityQueue<String> queue1 = new PriorityQueue<>();
queue1.offer("Oklahoma");
queue1.offer("Indiana");
queue1.offer("Georgia");
queue1.offer("Texas");
System.out.println("Priority queue using Comparable:");
while (queue1.size() > 0) {
    System.out.print(queue1.remove() + " ");
}
PriorityQueue<String> queue2 = new PriorityQueue(4, Collections.reverseOrder());
queue2.offer("Oklahoma");
queue2.offer("Indiana");
queue2.offer("Georgia");
queue2.offer("Texas");
System.out.println("\nPriority queue using Comparator:");
while (queue2.size() > 0) {
    System.out.print(queue2.remove() + " ");
}

Вывод:

Priority queue using Comparable:
Georgia Indiana Oklahoma Texas 
Priority queue using Comparator:
Texas Oklahoma Indiana Georgia

Else, вы также можете определить Custom Comparator:

import java.util.Comparator;

public class StringLengthComparator implements Comparator<String>
{
    @Override
    public int compare(String x, String y)
    {
        //Your Own Logic
    }
}

Ответ 11

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

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

public class PQExample {

    public static void main(String[] args) {
        //PriorityQueue with Comparator
        Queue<Customer> cpq = new PriorityQueue<>(7, idComp);
        addToQueue(cpq);
        pollFromQueue(cpq);
    }

    public static Comparator<Customer> idComp = new Comparator<Customer>(){

        @Override
        public int compare(Customer o1, Customer o2) {
            return (int) (o1.getId() - o2.getId());
        }

    };

    //utility method to add random data to Queue
    private static void addToQueue(Queue<Customer> cq){
        Random rand = new Random();
        for(int i=0;i<7;i++){
            int id = rand.nextInt(100);
            cq.add(new Customer(id, "KV"+id));
        }
    }


    private static void pollFromQueue(Queue<Customer> cq){
        while(true){
            Customer c = cq.poll();
            if(c == null) break;
            System.out.println("Customer Polled : "+c.getId() + " "+ c.getName());
        }
    }

}

Ответ 12

Передайте его Comparator. Заполните нужный тип вместо T

Использование lambdas (Java 8 +):

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, (e1, e2) -> { return e1.compareTo(e2); });

Классический способ, используя анонимный класс:

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, new Comparator<T> () {

    @Override
    public int compare(T e1, T e2) {
        return e1.compareTo(e2);
    }

});

Чтобы отсортировать в обратном порядке, просто замените e1, e2.