betacode

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

  1. PriorityQueue
  2. Examples

1. PriorityQueue

PriorityQueue - это класс, реализующий interface Queue, поэтому он обладает всеми характеристиками очереди и поддерживает все опциональные операции of Collection. Однако, в отличие от обычной очереди, элементы of PriorityQueue сортируются в порядке возрастания на основе их естественного порядка или в соответствии с предоставленным Comparator (в зависимости от используемого конструктора), поэтому, когда новый элемент вставляется в PriorityQueue, он может находиться не в последней позиции.
Характеристики, унаследованные от 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.
// Methods inherited from Collection:

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

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.
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 упоминаются в следующей статье: