Руководство Java PriorityQueue

PriorityQueue
Examples

1. PriorityQueue

PriorityQueue - это класс, реализующий interface Queue, поэтому он обладает всеми характеристиками очереди и поддерживает все опциональные операции of Collection. Однако, в отличие от обычной очереди, элементы of PriorityQueue сортируются в порядке возрастания на основе их естественного порядка или в соответствии с предоставленным Comparator (в зависимости от используемого конструктора), поэтому, когда новый элемент вставляется в PriorityQueue, он может находиться не в последней позиции.

Руководство Java Queue

Характеристики, унаследованные от Queue:

Повторяющиеся элементы разрешены, но элементы null не разрешены.

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable

PriorityQueue - это неограниченная (unbounded) очередь. Элементы сортируются в порядке возрастания, и допускается дублирование элементов.

В основном, PriorityQueue управляет массивом объектов (Object[]) для хранения его элементов. Длина этого массива больше, чем количество элементов очереди. Однако при необходимости этот массив будет заменен другим массивом большей длины.

PriorityQueue constructors

PriorityQueue()    

PriorityQueue(int initialCapacity)    

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

PriorityQueue(Collection<? extends E> c)    

PriorityQueue(Comparator<? super E> comparator)    

PriorityQueue(PriorityQueue<? extends E> c)    

PriorityQueue(SortedSet<? extends E> c)

Конструктор PriorityQueue(int initialCapacity) создает объект PriorityQueue с внутренним массивом размера initialCapacity. В этом случае все элементы of PriorityQueue должны быть типа Comparable, чтобы иметь возможность сравнивать себя, и элементы null не допускаются.
Конструктор PriorityQueue(Comparator) создает объект PriorityQueue с размером внутреннего массива по умолчанию 11. В то же время он снабжен Comparator для сравнения элементов друг с другом.

PriorityQueue - это асинхронная очередь, поэтому вы не должны использовать ее в среде multithreading, вместо этого используйте потокобезопасный (thread-safe) класс PriorityBlockingQueue.

Руководство Java PriorityBlockingQueue

// Methods inherited from Collection:

Iterator<E> iterator()
default Spliterator<E> spliterator()

Iterator, полученный из PriorityQueue, поддерживает все опциональные методы.
Iterator (или Spliterator), полученный из PriorityQueue, не гарантирует, что он будет проходить (traverse) элементы в порядке приоритета. Если вы хотите перебирать элементы в порядке приоритета, рассмотрите возможность использования Arrays.sort(priorityQueue.toArray()).

Queue
Deque
ConcurrentLinkedQueue
BlockingDeque
BlockingQueue
TransferQueue
ArrayDeque
ConcurrentLinkedDeque
LinkedList
ArrayBlockingQueue
DelayQueue
LinkedBlockingQueue
LinkedBlockingDeque
PriorityBlockingQueue
SynchronousQueue
LinkedTransferQueue

2. Examples

String является самосопоставимым типом данных, поскольку он реализует interface Comparable. Таким образом, нет необходимости предоставлять Comparator для PriorityQueue<String>.

PriorityQueueEx1.java

package org.o7planning.priorityqueue.ex;

import java.util.PriorityQueue;

public class PriorityQueueEx1 {

    public static void main(String[] args) {  
        PriorityQueue<String> queue = new PriorityQueue<>();

        queue.add("F");
        queue.add("D");
        queue.add("B");
        queue.add("A");
        queue.add("C");

        String s = null;
        
        // Retrieves and removes the head of this queue
        while((s = queue.poll())!= null)  {
            System.out.println(s);
        }
    }
}

Output:

A
B
C
D
F

Например: Класс Customer свойствами fullName, loyaltyPoints (Полное имя, накопленные баллы при покупке). Клиентам с более высокими баллами loyaltyPoints будет предоставлен более высокий приоритет.

Customer.java

package org.o7planning.beans;

public class Customer implements Comparable<Customer> {
    private String fullName;
    private int loyaltyPoints;

    public Customer(String fullName, int pointOfPurchase) { //
        this.fullName = fullName;
        this.loyaltyPoints = pointOfPurchase;
    }

    public String getFullName() {
        return fullName;
    }

    public int getLoyaltyPoints() {
        return loyaltyPoints;
    }

    @Override
    public int compareTo(Customer other) {
        if (other == null) {
            return -1; // this < other
        }
        int delta = this.loyaltyPoints - other.loyaltyPoints;
        if (delta != 0) {
            return - delta;
        }  
        return this.fullName.compareTo(other.fullName);
    }
}

PriorityQueueEx2.java

package org.o7planning.priorityqueue.ex;

import java.util.PriorityQueue;

import org.o7planning.beans.Customer;

public class PriorityQueueEx2 {

    public static void main(String[] args) {
        Customer tom = new Customer("Tom", 200);
        Customer jerry = new Customer("Jerry", 50);
        Customer donald = new Customer("Donald", 300);
        Customer mickey = new Customer("Mickey", 30);
        Customer daffy = new Customer("Daffy", 500);
        
        PriorityQueue<Customer> queue = new PriorityQueue<>();
        
        queue.add(tom);
        queue.add(jerry);
        queue.add(donald);
        queue.add(mickey);
        queue.add(daffy);
        
        Customer currentCustomer = null;
        
        while((currentCustomer = queue.poll())!= null) { // Retrieves and removes
            System.out.println("--- Serving customer: " + currentCustomer.getFullName() + " ---");
            System.out.println("   >> Loyalty Points: " + currentCustomer.getLoyaltyPoints());
            System.out.println();
        }
    }
}

Output:

--- Serving customer: Daffy ---
   >> Loyalty Points: 500

--- Serving customer: Donald ---
   >> Loyalty Points: 300

--- Serving customer: Tom ---
   >> Loyalty Points: 200

--- Serving customer: Jerry ---
   >> Loyalty Points: 50

--- Serving customer: Mickey ---
   >> Loyalty Points: 30

Например: Для элементов, которые не являются самосопоставимыми, необходимо предоставить Comparator для PriorityQueue.

Сравнение и Сортировка в Java

PriorityQueueEx3.java

package org.o7planning.priorityqueue.ex;

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueEx3 {

    public static void main(String[] args) {

        Employee tom = new Employee("Tom", 2000);
        Employee jerry = new Employee("Jerry", 500);
        Employee donald = new Employee("Donald", 3000);
        Employee mickey = new Employee("Mickey", 2000);
        Employee daffy = new Employee("Daffy", 5000);

        PriorityQueue<Employee> queue = new PriorityQueue<>(new EmployeeComparator());

        queue.add(tom);
        queue.add(jerry);
        queue.add(donald);
        queue.add(mickey);
        queue.add(daffy);

        Employee currentEmployee = null;

        while ((currentEmployee = queue.poll()) != null) { // Retrieves and removes
            System.out.println("--- Serving employee: " + currentEmployee.getFullName() + " ---");
            System.out.println("   >> Salary: " + currentEmployee.getSalary());
            System.out.println();
        }
    }
}

class Employee {
    private String fullName;
    private int salary;

    public Employee(String fullName, int salary) {
        this.fullName = fullName;
        this.salary = salary;
    }

    public String getFullName() {
        return fullName;
    }

    public int getSalary() {
        return salary;
    }
}

class EmployeeComparator implements Comparator<Employee> {

    @Override
    public int compare(Employee o1, Employee o2) {
        if (o1 == o2) {
            return 0;
        }
        if (o1 == null) {
            return -1; // o1 < o2
        }
        if (o2 == null) {
            return 1; // o1 > o2
        }
        int s = o1.getSalary() - o2.getSalary();
        if (s != 0) {
            return s;
        }
        return o1.getFullName().compareTo(o2.getFullName());
    }
}

Output:

--- Serving employee: Jerry ---
   >> Salary: 500

--- Serving employee: Mickey ---
   >> Salary: 2000

--- Serving employee: Tom ---
   >> Salary: 2000

--- Serving employee: Donald ---
   >> Salary: 3000

--- Serving employee: Daffy ---
   >> Salary: 5000

Если вы хотите выполнить итерацию по всем элементам of PriorityQueue, не удаляя их, вы можете использовать Iterator или Spliterator, но они не гарантируют порядок приоритета элементов. В этом случае следует использовать Arrays.sort(priorityQueue.toArray()) или Arrays.sort(priorityQueue.toArray(),comparator).

PriorityQueueEx4.java

package org.o7planning.priorityqueue.ex;

import java.util.Arrays;
import java.util.Iterator;
import java.util.PriorityQueue;

public class PriorityQueueEx4 {

    public static void main(String[] args) {

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

        queue.add("F");
        queue.add("D");
        queue.add("B");
        queue.add("A");
        queue.add("C");

        System.out.println("--- Using Iterator: ---");
        
        Iterator<String> ite = queue.iterator();
        
        while(ite.hasNext()) {
            String e = ite.next();
            System.out.println(e);
        }
        System.out.println("--- Using Arrays.sort(queue.toArray()): ----");
        
        String[] array = new String[queue.size()];
        queue.toArray(array);
        
        Arrays.sort(array);
        
        for(String e: array) {
            System.out.println(e);
        }
    }
}

Output:

--- Using Iterator: ---
A
B
D
F
C
--- Using Arrays.sort(queue.toArray()): ----
A
B
C
D
F

В принципе, в дополнение к вышеупомянутым характеристикам PriorityQueue обладает всеми характеристиками of Queue. Методы и связанные с ними примеры о Queue упоминаются в следующей статье:

Руководство Java Queue

Руководство Java PriorityQueue

1. PriorityQueue

2. Examples

Руководства Java Collections Framework

Руководства Java Collections Framework

Новейшие статьи