Chào ace, bài này chúng ta sẽ tìm hiểu về Priority Q ueue – Hàng đợi ưu tiên trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.
Priority Queue – Hàng đợi ưu tiên là một giải pháp mở rộng của Queue – Hàng đợi, với các thuộc tính sau:
– Mọi phần tử đều được gắn liền với một độ ưu tiên
– Một phần tử có độ ưu tiên cao sẽ được dequeued (xóa khỏi Priority Queue) trước một phần tử có độ ưu tiên thấp
– Nếu hai phần tử có cùng độ ưu tiên, lúc này việc phần tử nào được xử lý trước sẽ phụ thuộc vào thứ tự của chúng ở trong Priority Queue.
Trong Priority Queue dưới đây, phần tử có giá trị ASCII lớn nhất sẽ có độ ưu tiên cao nhất.
Một Priority Queue điển hình/thông thường sẽ hỗ trợ các thao tác xử lý dữ liệu sau:
– insert(item, priority): Chèn thêm một phần tử với độ ưu tiên cụ thể
– getHighestPriority(): Trả về phần tử có độ ưu tiên cao nhất
– deleteHighestPriority(): Xóa đi/loại bỏ đi phần tử có độ ưu tiên cao nhất.
Nội dung chính
1. Cách cài đặt Priority Queue – Hàng đợi ưu tiên
1. Cài đặt Priority Queue bằng Array – Mảng một chiều
Có thể cài đặt Priority Queue đơn giản bằng một mảng một chiều chứa các phần tử có cấu trúc giống như struct sau đây:
struct item {
int item;
int priority;
}
– Thao tác insert() có thể được cài đặt bằng cách chèn thêm một phần tử vào cuối mảng trong khoảng thời gian là O(1).
– getHighestPriority() có thể được cài đặt bằng cách tìm kiếm tuyến tính phần tử có độ ưu tiên cao nhất trong mảng. Thao tác này tốn O(n) thời gian.
– deleteHighestPriority() có thể được cài đặt bằng cách đầu tiên tìm kiếm tuyến tính phần tử có độ ưu tiên cao nhất trong mảng, sau đó loại bỏ phần tử ấy ra khỏi mảng bằng cách di chuyển tất cả các phần tử nằm sau nó lùi lại một đơn vị vị trí.
Chúng ta cũng có thể sử dụng Linked List để cài đặt Priority Queue, độ phức tạp về thời gian của tất cả các phép xử lý dữ liệu với Linked List vẫn sẽ giống như khi dùng mảng một chiều. Lợi thế của việc sử dụng Linked List đó là hàm deleteHighestPriority() có thể sẽ hiệu quả hơn vì chúng ta không cần phải dịch chuyển lùi lại các phần tử nữa.
2. Sử dụng Heaps
Cấu trúc dữ liệu Heap thường được ưu tiên sử dụng để cài đặt Priority Queue bởi vì Heap cung cấp hiệu năng tốt hơn khi so với mảng hay Linked List.
– Trong một Binary Heap, hàm getHighestPriority() có thể được cài đặt để có độ phức tạp thời gian là O(1), hàm insert() có thể được cài đặt với độ phức tạp thời gian là O(Logn) và hàm deleteHighestPriority() cũng có thể được cài đặt để có độ phức tạp thời gian là O(Logn).
– Với Fibonacci Heap, hàm insert() và hàm getHighestPriority() có thể được cài đặt với độ phức tạp về thời gian là O(1), và hàm deleteHighestPriority() có thể được cài đặt với độ phức tạp về thời gian là O(Logn).
3. Các ứng dụng của Priority Queue
1. Lập lịch CPU
2. Các Grapth algorithms – thuật toán Đồ thị như thuật toán tìm đường đi ngắn nhất Dijkstra, thuật toán Prim tìm cây khung nhỏ nhất, v.v…
3. Tất cả các ứng dụng xếp hàng có liên quan đến mức độ ưu tiên.
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
 và giải thuật, sau đây cafedev sẽ giới thiệu){kind=link}