PriorityQueue trong Java (Java PriorityQueue)

1. PriorityQueue là gì?

PriorityQueue là một lớp trong Java thuộc gói java.util. Nó đại diện cho một hàng đợi ưu tiên dựa trên heap (cây nhị phân), trong đó các phần tử được xử lý theo mức độ ưu tiên thay vì thứ tự chèn vào (FIFO – First In First Out).

2. Đặc điểm chính của PriorityQueue

• Sắp xếp phần tử tự động:
  • Theo mặc định, các phần tử trong PriorityQueue được sắp xếp theo thứ tự tăng dần tự nhiên (đối với các lớp triển khai Comparable như Integer, String, v.v.).
  • Bạn có thể tùy chỉnh thứ tự sắp xếp bằng cách cung cấp một bộ so sánh tùy chỉnh (Comparator) trong khi khởi tạo.
• Không đảm bảo thứ tự chèn (insertion order): Phần tử có độ ưu tiên cao nhất sẽ luôn được xử lý trước, không quan trọng nó được thêm vào lúc nào.
• Không cho phép phần tử null: Không được thêm giá trị null vào PriorityQueue.
• Hiệu suất cao:
  • Các thao tác như thêm (add() hoặc offer()) và lấy/xóa phần tử có độ ưu tiên cao nhất (poll()) được thực hiện trong thời gian O(log n).
  • Lấy phần tử đầu tiên (có độ ưu tiên cao nhất) mà không xóa (peek()) thực hiện trong thời gian O(1).
• Không đồng bộ: PriorityQueue không an toàn cho môi trường đa luồng. Nếu cần sử dụng trong môi trường đa luồng, bạn nên sử dụng PriorityBlockingQueue.

3. Một số phương thức quan trọng

• Thêm phần tử: add(E e) hoặc offer(E e): Thêm phần tử vào hàng đợi ưu tiên.
• Lấy phần tử:
  • poll(): Lấy và xóa phần tử có độ ưu tiên cao nhất khỏi hàng đợi.
  • peek(): Lấy nhưng không xóa phần tử có độ ưu tiên cao nhất.
• Xóa phần tử: remove(Object o): Xóa phần tử cụ thể khỏi hàng đợi.
• Kiểm tra kích thước: size(): Trả về số lượng phần tử trong hàng đợi.

4. Cách sử dụng PriorityQueue

Sử dụng thứ tự tự nhiên:

import java.util.PriorityQueue;

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

        // Thêm phần tử
        pq.add(10);
        pq.add(20);
        pq.add(15);

        System.out.println("PriorityQueue ban đầu: " + pq);

        // Lấy phần tử có độ ưu tiên cao nhất (nhỏ nhất trong trường hợp này)
        System.out.println("Phần tử nhỏ nhất: " + pq.peek());

        // Lấy và xóa phần tử nhỏ nhất
        System.out.println("Lấy và xóa phần tử nhỏ nhất: " + pq.poll());

        System.out.println("PriorityQueue sau khi xóa: " + pq);
    }
}

– Kết quả in ra:

PriorityQueue ban đầu: [10, 20, 15]
Phần tử nhỏ nhất: 10
Lấy và xóa phần tử nhỏ nhất: 10
PriorityQueue sau khi xóa: [15, 20]

Sử dụng Comparator tùy chỉnh (đảo ngược thứ tự):

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

public class App {

    public static void main(String[] args) {

        // Hàng đợi ưu tiên với thứ tự giảm dần
        PriorityQueue pq = new PriorityQueue<>(Comparator.reverseOrder());

        // Thêm phần tử
        pq.add(11);
        pq.add(22);
        pq.add(33);

        System.out.println("PriorityQueue ban đầu: " + pq);

        // Lấy phần tử có độ ưu tiên cao nhất (lớn nhất trong trường hợp này)
        System.out.println("Phần tử lớn nhất: " + pq.peek());

        // Lấy và xóa phần tử lớn nhất
        System.out.println("Lấy và xóa phần tử lớn nhất: " + pq.poll());

        System.out.println("PriorityQueue sau khi xóa: " + pq);
    }
}

– Kết quả in ra:

PriorityQueue ban đầu: [33, 11, 22]
Phần tử lớn nhất: 33
Lấy và xóa phần tử lớn nhất: 33
PriorityQueue sau khi xóa: [22, 11]

5. Khi nào nên sử dụng PriorityQueue?

• Cần xử lý các phần tử theo độ ưu tiên:
  • Ví dụ: Một hàng đợi tác vụ trong hệ điều hành (các tác vụ quan trọng được xử lý trước).
• Không quan tâm đến thứ tự chèn:
  • PriorityQueue sắp xếp dựa trên độ ưu tiên, không dựa trên thứ tự chèn.
• Hiệu suất tốt:
  • Khi cần một cấu trúc dữ liệu gọn nhẹ và nhanh để xử lý các phần tử theo thứ tự ưu tiên.

6. Câu hỏi phỏng vấn PriorityQueue

Cơ bản về PriorityQueue

• PriorityQueue là gì trong Java?
  • PriorityQueue là một cấu trúc dữ liệu trong Java, thực hiện dựa trên một hàng đợi ưu tiên (priority queue), nơi các phần tử được truy xuất theo thứ tự ưu tiên, chứ không phải theo thứ tự chúng được chèn vào.
• PriorityQueue được triển khai dựa trên cấu trúc dữ liệu nào?
  • PriorityQueue trong Java được triển khai dựa trên một heap (binary heap). Mặc định, nó là một min-heap.
• Sự khác biệt giữa Queue và PriorityQueue là gì?
  • Queue thực hiện theo nguyên tắc FIFO (First In, First Out), trong khi PriorityQueue ưu tiên phần tử dựa trên thứ tự ưu tiên được xác định bởi natural ordering hoặc một Comparator được cung cấp.

Vận hành và API của PriorityQueue

• Làm thế nào để chèn phần tử vào PriorityQueue?
  • Sử dụng phương thức add() hoặc offer().
• Làm thế nào để lấy phần tử ưu tiên cao nhất trong PriorityQueue mà không xóa nó?
  • Sử dụng phương thức peek().
• Làm thế nào để lấy và xóa phần tử ưu tiên cao nhất trong PriorityQueue?
  • Sử dụng phương thức poll() hoặc remove().
• Nếu thêm một phần tử null vào PriorityQueue thì điều gì sẽ xảy ra?
  • PriorityQueue không cho phép phần tử null, vì null không thể được so sánh để xác định thứ tự ưu tiên. Thao tác này sẽ gây ra ngoại lệ NullPointerException.

Ứng dụng Comparator

• Làm thế nào để tùy chỉnh thứ tự ưu tiên trong PriorityQueue?
• Natural ordering trong PriorityQueue được xác định như thế nào?

Hiệu suất và hạn chế

• Độ phức tạp thời gian của các thao tác chính trong PriorityQueue là gì?
  • Thêm (add/offer): O(log n)
  • Lấy và xóa phần tử ưu tiên cao nhất (poll): O(log n)
  • Lấy phần tử ưu tiên cao nhất mà không xóa (peek): O(1)
• PriorityQueue có hỗ trợ duyệt phần tử theo thứ tự ưu tiên không?
  • Không trực tiếp. Duyệt qua PriorityQueue bằng iterator không đảm bảo thứ tự ưu tiên.
• PriorityQueue có phải là thread-safe không?
  • Không, PriorityQueue không phải thread-safe. Nếu cần đồng bộ hóa, bạn có thể sử dụng PriorityBlockingQueue từ thư viện java.util.concurrent.

Các tình huống ứng dụng thực tế

• Khi nào sử dụng PriorityQueue thay vì ArrayList hoặc LinkedList?
  • Khi bạn cần truy xuất phần tử dựa trên thứ tự ưu tiên thay vì thứ tự chèn.
• Có thể sử dụng PriorityQueue để sắp xếp mảng không? Nếu có, làm thế nào?
  • Có, bằng cách thêm tất cả các phần tử của mảng vào PriorityQueue và sau đó liên tục gọi poll() để lấy phần tử theo thứ tự sắp xếp.

    int[] arr = {5, 1, 4, 3, 2};
    PriorityQueue pq = new PriorityQueue<>();
    for (int num : arr) {
        pq.offer(num);
    }
    while (!pq.isEmpty()) {
        System.out.print(pq.poll() + " ");
    }

Các câu hỏi nâng cao

• Làm thế nào để tạo một PriorityQueue của các đối tượng tùy chỉnh?
  • Triển khai Comparable hoặc cung cấp một Comparator. Ví dụ:

    public class Task implements Comparable {
        int priority;
        String name;
    
        public Task(int priority, String name) {
            this.priority = priority;
            this.name = name;
        }
    
        @Override
        public int compareTo(Object o) {
            return Integer.compare(priority, ((Task) o).priority);
        }
    }
    PriorityQueue pq = new PriorityQueue<>();
    pq.offer(new Task(2, "Task 1"));
    pq.offer(new Task(1, "Task 2"));
    

• Làm thế nào để chuyển một PriorityQueue thành Max-Heap?
  • Truyền Comparator.reverseOrder() vào constructor khi khởi tạo:

    PriorityQueue maxHeap = new PriorityQueue<>(Comparator.reverseOrder());