Cấu trúc dữ liệu Priority Queue hoạt động như thế nào và tại sao nó thường được cài đặt dựa trên nền tảng Binary Heap thay vì sử dụng một Sorted Array thông thường?

Question

Accepted Answer

1. Khái niệm Priority Queue
Priority Queue (Hàng đợi ưu tiên) là một dạng cấu trúc dữ liệu trừu tượng tương tự như Queue thông thường, nhưng mỗi phần tử sẽ đi kèm với một mức độ ưu tiên (priority). Phần tử có độ ưu tiên cao nhất sẽ luôn được lấy ra trước tiên.
2. So sánh hiệu năng giữa Sorted Array và Binary Heap

Sử dụng Sorted Array:
Thêm phần tử (Insert): O(N) vì phải tìm vị trí đúng để chèn nhằm duy trì tính có thứ tự.
Lấy phần tử ưu tiên cao nhất (Extract-Max/Min): O(1) nếu lấy ở đầu hoặc cuối mảng.

Sử dụng Binary Heap:
Thêm phần tử (Insert): O(log N) bằng thao tác nổi lên (Up-heap/Percolate-up).
Lấy phần tử ưu tiên cao nhất (Extract): O(log N) bằng thao tác chìm xuống (Down-heap/Percolate-down).

3. Tại sao chọn Binary Heap cho Enterprise?
Mặc dù Sorted Array cho phép lấy phần tử nhanh ở mức O(1), nhưng thao tác thêm mới tốn tới O(N). Trong các hệ thống thực tế (ví dụ: quản lý tiến trình hệ điều hành, thuật toán đường đi ngắn nhất Dijkstra), tần suất thêm và lấy phần tử diễn ra liên tục. Binary Heap cung cấp độ cân bằng tốt hơn với cả hai thao tác đều đạt O(log N), tránh tình trạng thắt cổ chai hiệu năng khi lượng dữ liệu lớn.

Cấu trúc dữ liệu Priority Queue hoạt động như thế nào và tại sao nó thường được cài đặt dựa trên nền tảng Binary Heap thay vì sử dụng một Sorted Array thông thường?

1. Khái niệm Priority Queue

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi data structures liên quan cùng chủ đề