Java Priority Queue là gì?

Priority Queue (Hàng đợi ưu tiên) trong Java là một cấu trúc dữ liệu đặc biệt cho phép các phần tử được xử lý theo thứ tự ưu tiên. Thay vì đơn giản là FIFO (First-In-First-Out) như trong hàng đợi thông thường, Priority Queue sắp xếp các phần tử dựa trên giá trị của chúng, cho phép phần tử có ưu tiên cao nhất được xử lý trước. Bài viết này sẽ giải thích chi tiết về Priority Queue, cách hoạt động và cách sử dụng trong Java.

1. Định nghĩa Priority Queue

1.1. Đặc điểm của Priority Queue

• Ưu tiên: Các phần tử trong hàng đợi được xử lý theo thứ tự ưu tiên chứ không phải theo thứ tự thêm vào. Phần tử có ưu tiên cao nhất (hoặc thấp nhất, tùy thuộc vào cách cài đặt) sẽ được lấy ra trước.
• Không đảm bảo thứ tự thêm vào: Nếu hai phần tử có cùng mức ưu tiên, thứ tự xử lý của chúng sẽ không được đảm bảo. Điều này có thể khác nhau giữa các thực thi.

1.2. Cấu trúc dữ liệu

Java sử dụng một cây nhị phân (binary heap) để cài đặt Priority Queue. Điều này cho phép thêm và loại bỏ phần tử có ưu tiên cao nhất một cách hiệu quả.

2. Cách hoạt động của Priority Queue

2.1. Thêm phần tử

Khi một phần tử mới được thêm vào hàng đợi, nó sẽ được đặt ở vị trí thích hợp trong cấu trúc để đảm bảo rằng hàng đợi vẫn giữ được tính chất ưu tiên.

2.2. Lấy phần tử

Khi lấy phần tử ra khỏi hàng đợi, phần tử có ưu tiên cao nhất sẽ được loại bỏ. Điều này thường liên quan đến việc sắp xếp lại cấu trúc dữ liệu để giữ cho hàng đợi trong trạng thái ưu tiên.

2.3. So sánh ưu tiên

Java cung cấp nhiều cách để xác định ưu tiên của phần tử:

• Natural Ordering: Sử dụng phương thức compareTo() trong lớp của phần tử.
• Custom Comparator: Cung cấp một Comparator tùy chỉnh khi tạo hàng đợi.

3. Cách sử dụng Priority Queue trong Java

3.1. Khởi tạo Priority Queue

Dưới đây là cách khởi tạo Priority Queue trong Java:

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(10);
        pq.add(20);
        pq.add(15);

        // Lấy và loại bỏ phần tử có ưu tiên cao nhất
        System.out.println("Phần tử có ưu tiên cao nhất: " + pq.poll()); // In ra 10
    }
}

3.2. Sử dụng Comparator

Bạn có thể sử dụng một Comparator tùy chỉnh để thay đổi cách mà các phần tử được sắp xếp trong hàng đợi. Ví dụ, dưới đây là cách tạo một hàng đợi mà trong đó phần tử lớn nhất có ưu tiên cao nhất:

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

public class Main {
    public static void main(String[] args) {
        // Tạo PriorityQueue với Comparator
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

        pq.add(10);
        pq.add(20);
        pq.add(15);

        // Lấy và loại bỏ phần tử có ưu tiên cao nhất
        System.out.println("Phần tử có ưu tiên cao nhất: " + pq.poll()); // In ra 20
    }
}

3.3. Một số phương thức hữu ích

• add(E e): Thêm một phần tử vào hàng đợi.
• poll(): Lấy và loại bỏ phần tử có ưu tiên cao nhất.
• peek(): Lấy phần tử có ưu tiên cao nhất mà không loại bỏ nó.
• size(): Trả về số lượng phần tử trong hàng đợi.
• isEmpty(): Kiểm tra xem hàng đợi có rỗng hay không.

4. Ứng dụng của Priority Queue

Priority Queue có nhiều ứng dụng thực tế, bao gồm:

• Quản lý tài nguyên: Trong lập trình đa luồng, Priority Queue có thể được sử dụng để quản lý các tác vụ và phân bổ tài nguyên.
• Thuật toán tìm kiếm: Nhiều thuật toán tìm kiếm như Dijkstra hay A* sử dụng hàng đợi ưu tiên để xử lý các đỉnh theo trọng số.
• Quản lý sự kiện: Trong các hệ thống xử lý sự kiện, Priority Queue có thể được dùng để quản lý các sự kiện dựa trên thời gian hoặc ưu tiên.

5. Kết luận

Priority Queue trong Java là một cấu trúc dữ liệu mạnh mẽ cho phép bạn quản lý và xử lý các phần tử theo ưu tiên. Với khả năng tùy chỉnh qua Comparator, bạn có thể dễ dàng điều chỉnh hành vi của hàng đợi để phù hợp với nhu cầu cụ thể của mình. Hiểu và sử dụng Priority Queue hiệu quả có thể giúp tối ưu hóa hiệu suất và tính khả thi của ứng dụng.