PriorityQueue trong Java là một thành phần quan trọng của Collections Framework, cung cấp một cách hiệu quả để quản lý các phần tử dựa trên mức độ ưu tiên của chúng. Về cơ bản, nó được triển khai dưới dạng một cấu trúc dữ liệu heap. Mặc định, nếu không có Comparator tùy chỉnh nào được cung cấp, nó hoạt động như một min-heap (heap tối thiểu), nghĩa là phần tử nhỏ nhất sẽ luôn ở đầu hàng đợi.

Các phần tử trong hàng đợi này có thể được sắp xếp dựa trên thứ tự tự nhiên của chúng (nếu chúng triển khai giao diện Comparable) hoặc theo một Comparator tùy chỉnh được cung cấp khi khởi tạo. Phần tử đầu tiên của hàng đợi (head) luôn là phần tử 'nhỏ nhất' hoặc 'lớn nhất' theo tiêu chí sắp xếp đã định. Nếu có nhiều phần tử cùng 'nhỏ nhất' hoặc 'lớn nhất', bất kỳ phần tử nào trong số đó cũng có thể là head.

Khi khởi tạo, có thể cung cấp một dung lượng ban đầu, nhưng PriorityQueue sẽ tự động điều chỉnh kích thước khi cần thiết, cho phép nó chứa một số lượng phần tử động.

Lưu ý quan trọng về PriorityQueue:

• Triển khai nội bộ: Mặc dù được triển khai dựa trên một mảng, PriorityQueue có khả năng tự động mở rộng kích thước, cung cấp dung lượng "vô hạn" về mặt lý thuyết.
• An toàn luồng: Việc triển khai PriorityQueue không được đồng bộ hóa và không an toàn cho môi trường đa luồng. Nếu nhiều luồng có thể sửa đổi cấu trúc của nó, cần đảm bảo đồng bộ hóa thủ công hoặc sử dụng lớp PriorityBlockingQueue để đảm bảo an toàn luồng.
• Giá trị null: Không cho phép chèn phần tử null vào PriorityQueue.
• Độ phức tạp thời gian:
  • Các thao tác chèn (như add(), offer()) và xóa (như poll(), remove()) có độ phức tạp thời gian O(log(n)).
  • Các phương thức remove(Object) và contains(Object) có độ phức tạp O(n).
  • Trong khi đó, các thao tác truy vấn (như peek(), element(), size()) chỉ mất thời gian hằng số O(1).
• Thứ tự của Iterator: Trình lặp trả về bởi phương thức iterator() không đảm bảo duyệt qua các phần tử theo thứ tự đã sắp xếp của hàng đợi. Để duyệt các phần tử theo thứ tự, có thể chuyển đổi hàng đợi thành mảng và sau đó sắp xếp mảng đó, ví dụ: Arrays.sort(queue.toArray()).
• Các hàm tạo: Cách sắp xếp có thể được chỉ định thông qua các hàm tạo khác nhau:
  • PriorityQueue(): Tạo một hàng đợi ưu tiên với dung lượng ban đầu mặc định (11) và sắp xếp các phần tử theo thứ tự tự nhiên của chúng (sử dụng Comparable).
  • PriorityQueue(int initialCapacity): Tạo hàng đợi ưu tiên với dung lượng ban đầu được chỉ định và sắp xếp theo thứ tự tự nhiên.
  • PriorityQueue(int initialCapacity, Comparator<? super E> comparator): Tạo hàng đợi ưu tiên với dung lượng ban đầu và sắp xếp các phần tử theo Comparator được cung cấp.
• Giao diện: Lớp PriorityQueue và trình lặp của nó triển khai tất cả các phương thức tùy chọn từ giao diện Collection và Iterator.

PriorityQueue sử dụng cấu trúc heap để duy trì thứ tự ưu tiên. Điều này có nghĩa là phần tử 'ưu tiên cao nhất' (nhỏ nhất trong min-heap, lớn nhất trong max-heap) luôn nằm ở gốc của heap (tức là phần tử đầu tiên của hàng đợi). Tuy nhiên, các phần tử còn lại trong cấu trúc heap không nhất thiết phải được sắp xếp hoàn toàn. Do đó, khi sử dụng iterator() để duyệt, các phần tử có thể không được trả về theo một thứ tự có ý nghĩa.

Ví dụ: Tùy chỉnh bộ so sánh (Comparator)

Để tạo một hàng đợi ưu tiên sắp xếp theo một tiêu chí không phải là thứ tự tự nhiên, bạn có thể cung cấp một Comparator tùy chỉnh. Ví dụ dưới đây minh họa cách tạo một hàng đợi ưu tiên cho số nguyên, sắp xếp các phần tử theo thứ tự giảm dần (tạo thành một max-heap):

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

public class CustomComparatorExample {
    public static void main(String[] args) {
        // Khởi tạo PriorityQueue với dung lượng ban đầu là 5
        // và một Comparator sắp xếp các số nguyên theo thứ tự giảm dần.
        Queue<Integer> hangDoiSoNguyenDaoNguoc = new PriorityQueue<>(5, 
            (soA, soB) -> soB.compareTo(soA) // Sử dụng lambda expression cho Comparator
        );

        hangDoiSoNguyenDaoNguoc.offer(10);
        hangDoiSoNguyenDaoNguoc.offer(2);
        hangDoiSoNguyenDaoNguoc.offer(8);
        hangDoiSoNguyenDaoNguoc.offer(15);
        hangDoiSoNguyenDaoNguoc.offer(5);

        System.out.println("Các phần tử từ hàng đợi (thứ tự giảm dần):");
        while (!hangDoiSoNguyenDaoNguoc.isEmpty()) {
            System.out.println(hangDoiSoNguyenDaoNguoc.poll());
        }
    }
}

Đoạn mã trên sẽ in ra các số theo thứ tự: 15, 10, 8, 5, 2.

Ví dụ hoàn chỉnh: Sắp xếp đối tượng tùy chỉnh

Dưới đây là một ví dụ minh họa cách sử dụng PriorityQueue để sắp xếp các đối tượng tùy chỉnh (ví dụ: HocSinh) dựa trên nhiều tiêu chí (điểm số, sau đó là tên) bằng cách sử dụng một Comparator tùy chỉnh.

import java.util.PriorityQueue;
import java.util.Random;

// Định nghĩa lớp đối tượng Học Sinh
class HocSinh {
    String ten;
    int diemSo;

    public HocSinh(String ten, int diemSo) {
        this.ten = ten;
        this.diemSo = diemSo;
    }

    @Override
    public String toString() {
        return "Tên: " + ten + ", Điểm số: " + diemSo;
    }
}

public class DemoPriorityQueue {
    public static void main(String[] args) {
        // Khởi tạo PriorityQueue cho các đối tượng HocSinh
        // Sắp xếp theo:
        // 1. DiemSo tăng dần (điểm thấp ưu tiên trước)
        // 2. Nếu DiemSo bằng nhau, sắp xếp theo Ten tăng dần (theo bảng chữ cái)
        PriorityQueue<HocSinh> danhSachHocSinh = new PriorityQueue<>(10, (hs1, hs2) -> {
            // So sánh theo DiemSo (tăng dần)
            int soSanhDiemSo = Integer.compare(hs1.diemSo, hs2.diemSo);
            if (soSanhDiemSo != 0) {
                return soSanhDiemSo;
            }
            // Nếu DiemSo bằng nhau, so sánh theo Ten (tăng dần)
            return hs1.ten.compareTo(hs2.ten);
        });

        Random rng = new Random();
        // Thêm một số học sinh vào hàng đợi
        for (int i = 0; i < 5; i++) {
            danhSachHocSinh.add(new HocSinh("SV" + (char)('A' + i), 60 + rng.nextInt(40))); // Điểm từ 60-99
        }

        // Thêm các học sinh có điểm số trùng lặp để kiểm tra tiêu chí sắp xếp phụ
        danhSachHocSinh.add(new HocSinh("SV_Beta", 85));
        danhSachHocSinh.add(new HocSinh("SV_Alpha", 85));
        danhSachHocSinh.add(new HocSinh("SV_Gamma", 85));
        danhSachHocSinh.add(new HocSinh("SV_Delta", 70));


        System.out.println("Danh sách học sinh theo thứ tự ưu tiên (điểm thấp trước, nếu bằng thì tên chữ cái nhỏ trước):");
        while (!danhSachHocSinh.isEmpty()) {
            System.out.println(danhSachHocSinh.poll().toString());
        }
    }
}