Hướng dẫn và ví dụ Java PriorityQueue

PriorityQueue
Examples

1. PriorityQueue

PriorityQueue là một lớp thi hành interface Queue nên nó có đầy đủ các đặc điểm của một hàng đợi và hỗ trợ tất cả các hoạt động tuỳ chọn của Collection. Tuy nhiên khác với một hàng đợi thông thường, các phần tử của PriorityQueue được xắp xếp theo một thứ tự tăng dần dựa trên thứ tự tự nhiên của chúng hoặc theo một Comparator được cung cấp (Tuỳ vào constructor được sử dụng), vì vậy khi một phần tử mới được chèn vào PriorityQueue nó có thể không ở vị trí cuối cùng.

Hướng dẫn và ví dụ Java Queue

Các đặc điểm thừa kế từ Queue:

Cho phép phần tử trùng lặp nhưng không cho phép phần tử null.

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

PriorityQueue là một hàng đợi không giới hạn (unbounded), các phần tử được xắp xếp theo thứ tự tăng dần và cho phép các phần tử trùng lặp.

Về cơ bản, PriorityQueue quản lý một mảng đối tượng (Object[]) để lưu trữ các phần tử của nó. Độ dài của mảng này lớn hơn so với số phần tử của hàng đợi, tuy nhiên mảng này sẽ được thay thế bởi một mảng khác có độ dài lớn hơn nếu cần thiết.

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)

Constructor PriorityQueue(int initialCapacity) tạo ra một đối tượng PriorityQueue với mảng nội bộ có kích thước initialCapacity. Trường hợp này tất cả các phần tử của PriorityQueue phải là kiểu Comparable để có thể tự so sánh với nhau, và phần tử null là không được phép.
Constructor PriorityQueue(Comparator) tạo ra một đối tượng PriorityQueue với kích thước mảng nội bộ mặc định là 11, đồng thời nó được cung cấp một Comparator để so sánh các phần tử với nhau.

PriorityQueue là một hàng đợi không được đồng bộ, vì vậy bạn không nên sử dụng nó trong môi trường multithreading, thay vào đó, hãy sử dụng lớp an toàn theo luồng (thread-safe) PriorityBlockingQueue.

Hướng dẫn và ví dụ Java PriorityBlockingQueue

// Methods inherited from Collection:

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

Iterator có được từ PriorityQueue hộ trợ tất cả các phương thức tuỳ chọn.
Iterator (hoặc Spliterator) có được từ PriorityQueue không đảm bảo rằng nó sẽ giúp duyệt qua (traverse) các phần tử theo thứ tự ưu tiên. Nếu muốn duyệt qua các phần tử theo thứ tự ưu tiên hãy cân nhắc sử dụng Arrays.sort(priorityQueue.toArray()).

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

2. Examples

String là kiểu dữ liệu có thể tự so sánh được với nhau vì nó thi hành interface Comparable. Vì vậy không cần cung cấp một Comparator cho 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

Ví dụ: Lớp Customer với các property fullName, loyaltyPoints (Họ tên, số điểm tích luỹ khi mua hàng). Khách hàng có loyaltyPoints cao hơn sẽ được ưu tiên phục vụ.

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

Ví dụ: Với các phần tử không thể tự so sánh với nhau, bạn cần cung cấp một Comparator cho PriorityQueue.

So sánh và sắp xếp trong 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

Nếu muốn duyệt qua tất cả các phần tử của một PriorityQueue mà không phải loại bỏ các phần tử, bạn có thể sử dụng Iterator hoặc Spliterator, tuy nhiên chúng không đảm báo thứ tự ưu tiên của các phần tử. Trong trường hợp này bạn nên sử dụng Arrays.sort(priorityQueue.toArray()) hoặc 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

Về cơ bản, ngoài các đặc điểm nói trên PriorityQueue có đầy đủ các đặc điểm của một Queue. Các phương thức và các ví dụ liên quan về Queue được đề cập trong bài viết dưới đây:

Hướng dẫn và ví dụ Java Queue

Hướng dẫn và ví dụ Java PriorityQueue

1. PriorityQueue

2. Examples

Các hướng dẫn Java Collections Framework

Các hướng dẫn Java Collections Framework