Có bao nhiêu cách cài đặt Hàng đợi ưu tiên?
Cấu trúc Hàng Đợi Ưu Tiên (priority queues) là một trong những CTDL kinh điển trong KHMT với rất nhiều ứng dụng khác nhau, có thể kể đến như:
- CTDL quan trọng cho các thuật toán khác như Dijkstra’s Algorithms.
- Numerical Optimization: một vài thuật toán optimization (đặc biệt là iterative optimization) phải chọn ra những biểu thức có sai số làm tròn cao nhất/thấp nhất để thực thi.
- Trong Hệ Điều Hành, các giải thuật lập lịch, scheduling.
- Trong các hệ thống giả lập, những sự kiện theo trình tự thời gian được ưu tiên thực thi trước.
Priority Queues có hai toán tử rất quan trọng:
- Chèn một phần tử vào queue (
find_max). - Lấy ra phần tử lớn nhất trong queue (
push).
Chính vì hai chức năng này nên đôi khi Priority queues còn được nhắc đến với cái
tên: Largest in, first out; (để phân biệt với First in, First out hay First in,
last out). Cụ thể hơn, nếu phần tử K[N] là phần tử lớn nhất được chèn vào, thì
K[N] cũng là phần tử đầu tiên được lấy ra.
Bởi tầm quan trọng của 2 hàm này, khi tiếp cận bất kì cài đặt nào liên quan đến priority queues, ta luôn quan tâm cách mà 2 toán tử này duy trì trạng thái trình tự của các phần tử trong CTDL, đó cũng là phần phân tích chính trong bài viết này.
Các phương pháp cài đặt
Toàn bộ các cài đặt bằng C++ và các phân tích được đề cập chi tiết trong note
Algorithms trên Github của mình. Trên blog mình chỉ tóm tắt sơ lược về các
cài đặt và một số fun facts xung quanh.
Danh sách bên dưới có một điều thú vị, đó là ta sẽ thấy độ thần thánh của R.Tarjan, ông đóng góp 4⁄12 cấu trúc được đề cập.
Cài đặt bằng mảng
Một cách đơn giản nhất khi sử dụng mảng đó là:
- Luôn giữ một mảng được sắp xếp,
find_maxđơn giản chỉ là lấy ra phần tử đầu hoặc cuối dãy. Khipush, ta sử dụng chiến lược tương tự nhưinsertion_sort. pushthực hiện như mảng bình thường. Khi gọifind_max, ta đơn giản tìm phần tử lớn nhất trong mảng đó.
Cả hai phương pháp đều có độ phức tạp $\mathcal{O}(1)$ và $\mathcal{O}(N)$ ứng
với find_max, push (cho trường hợp 1) và push,find_max (cho trường
hợp 2).
Một cách tốt hơn, khá dễ cài đặt là sử dụng heapsort với độ phức tạp là $\lg N$ cho cả 2 toán tử. Chi tiết về heapsort và heap trong priority queue thì quá kinh điển rồi, hầu như mọi sách về thuật toán đề có đề cập.
Leftist tree
Tác giả: Clark A. Crane (1971).
Một phương pháp cài đặt dạng danh sách liên kết, trong đó mỗi node có các phần tử như sau:
template<typename Key>
struct node {
node * left;
node * right;
int dist;
Key k;
};
Đây là cây nhị phân đặt biệt, trong đó cây con bên trái luôn nhiều phần tử hơn
cây con bên phải, việc này được duy trì thông qua việc câp nhật giá trị dist:
khoảng cách của node hiện tại tới node NULL gần nhất.
Chi tiết về thuật toán và cài đặt:
- TAoCP, Vol 3, Section 5.2.3: A linked representation for priority queues.
- Geeksforgeeks
Ưu điểm của CTDL này chính là việc nó có khả năng gộp 2 priority queues lại với độ phức tạp khá nhỏ. Tuy nhiên, CTDL này thực sự không còn phổ biến.
Cây cân bằng
Stratified tree
Cấu trúc dữ liệu này có một cái tên phổ biến hơn: van Emde boas tree [Rất tiếc trên Wikipedia, phần van Emde Boas tre lại không đề cập đến tên gọi gốc của CTDL này].
Beware of bugs in the above code; I have only proved it correct, not tried it
Câu nói kinh điển này của Don Knuth xuất phát từ việc ông trao đổi với tác giả của cấu trúc này [link 1], [link 2].
Binomial Queues
Tác giả: J. Vuillemin (1978).
Pagodas
Tác giả: J. Francon, G. Viennot, and J. Vuillemin (1978).
Pairing heaps
Tác giả: Micheal Fredman, Robert Sedgewick, Daniel Sleator, Robert Tarjan (1986).
Skew heaps
Fibonacci heaps và dạng tổng quát: AF heaps
Một trong những ví dụ kinh điển về những thuật toán/CTDL có tính chất rất tốt về mặt lý thuyết nhưng lại thất bại trong ứng dụng thực tiễn.