7.1 Priority Queue là gì?

Trong một số trường hợp, chúng ta có thể cần tìm phần tử tối thiểu/tối đa trong một tập hợp các phần tử. chúng ta có thể làm điều này với sự trợ giúp của Priority Queue ADT. Một priority queue ADT là một cấu trúc dữ liệu hỗ trợ các thao tác Insert và DeleteMin (trả về và loại bỏ phần tử nhỏ nhất) hoặc DeleteMax (trả về và loại bỏ phần tử lớn nhất).

Các thao tác này tương đương với thao tác EnQueue và DeQueue của một hàng đợi. Sự khác biệt là, trong hàng đợi ưu tiên, thứ tự mà các phần tử vào hàng đợi có thể không giống với thứ tự mà chúng được xử lý. Một ứng dụng ví dụ của hàng đợi ưu tiên là job scheduling(bài toán lập lịch), được ưu tiên thay vì phục vụ theo thứ tự đến trước phục vụ trước.

Tương tự, một hàng đợi ưu tiên được gọi là descending —priority queue(hàng đợi ưu tiên giảm dần) nếu phần tử có key lớn nhất có mức ưu tiên cao nhất (luôn xóa phần tử lớn nhất). Vì hai loại này đối xứng nên chúng ta sẽ tập trung vào một trong số chúng: ascending-priority queue(hàng đợi ưu tiên tăng dần).

7.2 Priority Queue ADT

Các thao tác sau đây làm cho hàng đợi ưu tiên trở thành ADT.

Các Operations chính trên Priority Queues Hàng đợi ưu tiên là một thùng chứa các phần tử, mỗi phần tử có một key được liên kết.

• Insert (key, data): Thêm dữ liệu cùng key vào priority queue.
• DeleteMin/DeleteMax: Xóa và trả về phần tử có key nhỏ nhất/lớn nhất.
• GetMinimum/GetMaximum: Trả về phần tử có khóa nhỏ nhất/lớn nhất mà không xóa nó.

Các Operations phụ trợ trên Priority Queues

• kth – Smallest/kth – Largest: Trả về khóa thứ k – Nhỏ nhất/Lớn nhất trong hàng đợi ưu tiên.
• Size: Trả về số phần tử trong hàng đợi ưu tiên.
• Heap Sort: Sắp xếp các phần tử trong hàng đợi ưu tiên dựa trên mức độ ưu tiên (khóa).

7.3 Ứng dụng của Priority Queue

Hàng đợi ưu tiên có nhiều ứng dụng – mình sẽ liệu kê một vài trong số chúng:

• Nén dữ liệu: thuật toán Huffman Coding
• Thuật toán đường đi ngắn nhất: Thuật toán Dijkstra
• Thuật toán cây bao trùm tối thiểu: Thuật toán Prim
• Mô phỏng theo hướng sự kiện: khách hàng xếp hàng
• Bài toán lựa chọn: Tìm phần tử nhỏ thứ k

7.4 Triển khai Priority Queue

Trước khi thảo luận về việc triển khai thực tế, chúng ta hãy liệt kê các tùy chọn khả thi trên lý thuyết.

Triển khai Unordered Array(mảng không có thứ tự)

Các phần tử được chèn vào mảng mà không cần quan tâm đến thứ tự. Việc xóa (DeleteMax) được thực hiện bằng cách tìm kiếm khóa và sau đó xóa.

Insertions complexity: O(1). DeleteMin complexity: O(n).

Triển khai Unordered List (List không có thứ tự)

Nó rất giống với triển khai mảng, nhưng thay vì sử dụng mảng, danh sách liên kết được sử dụng.

Insertions complexity: O(1). DeleteMin complexity: O(n).

Triển khai Ordered Array(mảng có thứ tự)

Các phần tử được chèn vào mảng theo thứ tự được sắp xếp dựa trên trường khóa. Việc xóa chỉ được thực hiện ở một đầu.

Insertions complexity: O(n). DeleteMin complexity: O(1).

Triển khai Ordered List(List có thứ tự)

Các phần tử được chèn vào danh sách theo thứ tự được sắp xếp dựa trên trường key. Việc xóa chỉ được thực hiện ở một đầu, do đó duy trì trạng thái của hàng đợi ưu tiên. Tất cả các chức năng khác được liên kết với linked list ADT được thực hiện mà không cần sửa đổi.

Insertions complexity: O(n). DeleteMin complexity: O(1).

Triển khai Binary Search Trees

Cả việc thêm và xóa đều lấy trung bình O(logn) nếu việc thêm vào là ngẫu nhiên (các bạn có thể tham khảo các bài về Tree mình đã trình bày ở phần trước).

Triển khai Balanced Binary Search Trees

Cả thao tác thêm và xóa đều lấy O(logn) trong trường hợp xấu nhất.

Triển khai Binary Heap

Trong các phần tiếp theo, chúng ta sẽ thảo luận chi tiết về điều này. Hiện tại, giả sử rằng việc triển khai heap nhị phân mang lại độ phức tạp O(logn) cho tìm kiếm, chèn và xóa và O(1) để tìm phần tử lớn nhất hoặc nhỏ nhất.

So sánh các loại triển khai