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 ⁴⁄₁₂ 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à:

1. 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. Khi push, ta sử dụng chiến lược tương tự như insertion_sort.
2. push thực hiện như mảng bình thường. Khi gọi find_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:

1. TAoCP, Vol 3, Section 5.2.3: A linked representation for priority queues.
2. 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.

Calendar queues

Relaxed heaps

Fishspear

Hot queues

So sánh