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.
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ả.
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.
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.
Java cung cấp nhiều cách để xác định ưu tiên của phần tử:
compareTo() trong lớp của phần tử.Comparator tùy chỉnh khi tạo hàng đợi.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
}
}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
}
}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.Priority Queue có nhiều ứng dụng thực tế, bao gồm:
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.
