Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 11: Hàng ưu tiên

i cây B2 còn lại thành một cây B3. Vì H3 chưa có cây nhị thức B3 nên B3 cuối 
cùng này sẽ là thành phần của H3. 
 H1 H2 
Hình 11.10- Hai hàng nhị thức H1 và H2. 
Hình 11.11 - Kết hợp hai cây nhị thức B1 trong H1 và H2. 
Hình 11.12- Kết quả trộn H1 và H2 thành H3. 
Việc kết hợp hai cây nhị thức tốn O(1), với O(log N) cây nhị thức trong mỗi 
hàng nhị thức, việc trộn hai hàng nhị thức cũng tốn O(log N) trong trường hợp 
xấu nhất. Để tăng tính hiệu quả, chúng ta lưu các cây nhị thức trong mỗi hàng 
nhị thức theo thứ tự tăng dần của chiều cao các cây. 
Việc thêm một phần tử mới vào hàng nhị thức tương tự như đối với heap lệch 
trái: trộn hàng nhị thức có duy nhất phần tử cần thêm với hàng nhị thức đã có. 
Việc loại phần tử nhỏ nhất cũng đơn giản: tìm phần tử nhỏ nhất trong số các 
nút gốc của các cây nhị thức. Giả sử đó là cây Bk. Sau khi loại bỏ nút gốc của cây 
Bk, chúng ta còn lại các cây con của nó: B0, B1, Bk-1. Gọi rừng gồm các cây con 
này là H’, và H’’ là hàng nhị thức ban đầu không kể BK. Việc cuối cùng cần làm là 
trộn H’ và H’’. Chúng ta có thể tự kiểm tra rằng các phép thêm và loại này đều 
tốn O(log N) trong trường hợp xấu nhất. 
16 
18 
12 
21 24 
65 
14 
26 
23 
51 24 
65 
13 
14 
26 16 
18 
23 
51 24 
65 
13 12 
21 24 
65 
14 
26 16 
18 
23
Chương 11 – Hàng ưu tiên 
Giáo trình Cấu trúc dữ liệu và Giải thuật 298
Hình 11.13- Quá trình thêm các phần tử 1, 2,, 7 vào hàng nhị thức. 
1 
2 3 
4 
1 
1 2 1 
2 
1 
2 
3 1 
2 
3 
1 
2 
3 4 1 
2 
3 
4 
1 
2 3 
4 
5 1 
2 3 
4 
5 
1 
2 3 
4 
5 6 1 
2 3 
4 
5 
6 
1 
2 3 
4 
5 
6 
7 1 
2 3 
4 
5 
6 
7 
Chương 11 – Hàng ưu tiên 
Giáo trình Cấu trúc dữ liệu và Giải thuật 299
 H 
 H’’ H’ 
Hình 11.14- Quá trình loại phần tử nhỏ nhất trong hàng nhị thức H. 
Hiện thực của hàng nhị thức 
Việc tìm phần tử nhỏ nhất cần duyệt qua các gốc của các cây nhị thức trong 
hàng nhị thức (12, 23 và 13 trong hình 11.14). Chúng ta có thể dùng danh sách 
liên kết để chứa các nút gốc này. Danh sách sẽ có thứ tự theo chiều cao của các 
cây nhị thức để phục vụ cho phép trộn hai hàng nhị thức được dễ dàng. 
Tương tự, các nút con của nút gốc của một cây nhị thức cũng được chứa trong 
một danh sách liên kết (14, 24 và 21 trong hình 11.14), để khi loại bỏ nút gốc 
(nút 12) thì phần còn lại cũng có cấu trúc tương tự như một hàng nhị thức mới, 
rất thuận lợi trong phép loại phần tử nhỏ nhất trong hàng nhị thức. 
Hình 11.15- Hàng nhị thức H 
23 
51 24 
65 
13 12 
21 24 
65 
14 
26 16 
18 
23 
51 24 
65 
13 21 24 
65 
14 
26 16 
18 
23 
51 24 
65 
13 
21 24 
65 
14 
26 16 
18 
23 
51 24 
65 
13 12 
21 24 
65 
14 
26 16 
18 
Chương 11 – Hàng ưu tiên 
Giáo trình Cấu trúc dữ liệu và Giải thuật 300
Hình 11.16- Hiện thực liên kết của hàng nhị thức H. 
Trong hình vẽ trên chúng ta thấy hình elipse nét rời biểu diễn các danh sách 
liên kết các nút mà chúng ta thường phải duyệt qua. Hình elipse nét rời lớn chứa 
các gốc của các cây nhị thức trong hàng nhị thức, khi cần tìm phần tử nhỏ nhất 
trong hàng nhị thức chúng ta tìm trong danh sách này. Hình elipse nét rời nhỏ 
chứa các nút con của nút gốc trong một cây nhị thức. 
Trong quá trình hình thành hàng nhị thức trong một số thao tác dữ liệu, khi 
kết hợp hai cây nhị thức có cùng chiều cao (hình 11.18), chúng ta cần nối một 
trong hai cây thành cây con của cây còn lại, mà cây con mới này cũng chính là 
cây con có chiều cao lớn nhất so với các cây con đã có. Việc chèn cây con mới vào 
đầu của danh sách liên kết sẽ thuận tiện hơn, vì vậy chúng ta cho danh sách này 
có thứ tự giảm dần theo chiều cao của các cây con (hình 11.18). 
Ngoài ra, mỗi nút trong cây nhị thức sẽ có một con trỏ cho phép truy xuất đến 
danh sách các con của nó. Tóm lại, hiện thực đơn giản và hiệu quả cho hàng nhị 
thức thật đơn giản như hình 11.18, đó là cấu trúc của một cây nhị phân, mỗi nút 
có con trỏ trái chỉ đến nút con đầu tiên của nó và con trỏ phải chỉ đến nút anh 
em của nó. 
Hình 11.17- Gốc các cây nhị thức được chứa trong mảng liên tục. 
Hình 11.17 là một phương án thay danh sách liên kết trên cùng bởi mảng liên 
tục. Chúng ta có thể dùng mảng liên tục cấp phát động để khắc phục nhược điểm 
do không biết trước chiều cao của cây nhị thức cao nhất trong hàng nhị thức. Việc 
dùng mảng liên tục cho phép tìm nhị phân phần tử nhỏ nhất, tuy nhiên sẽ là 
lãng phí lớn khi hàng nhị thức gồm quá ít cây nhị thức với nhiều chiều cao khác 
nhau. 
13 12 
14 24 
65 
21 
23 
51 24 
65 16 26 
18 
13 12 
14 24 
65 
21 
23 
51 24 
65 16 26 
18 
Chương 11 – Hàng ưu tiên 
Giáo trình Cấu trúc dữ liệu và Giải thuật 301
Hình 11.18- Kết hợp hai cây nhị thức B2 thành một cây nhị thức B3. 
Dưới đây là phần mã giả cho các khai báo cấu trúc của cây nhị thức và hàng 
nhị thức. Các tác vụ kết hợp hai cây nhị thức, trộn hai hàng nhị thức, và loại 
phần tử nhỏ nhất trong hàng nhị thức cũng được trình bày bằng mã giả. 
//Phần mã giả cho khai báo và một số tác vụ cho hàng nhị thức. 
struct Binomial_Node 
 DataType data 
 Binomial_Node* leftChild 
 Binomial_Node* nextSibling 
end struct 
struct Binomial_Tree 
 Binomial_Tree combineTrees(ref Binomial_Tree T1, ref Binomial_Tree T2) 
 Binomial_Node* root 
 int notEmpty() // Trả về 1 nếu cây không rỗng, ngược lại trả về 0. 
end struct 
class Binomial_Queue 
 public: 
 Binomial_Queue(Binomial_Node* p, int k)// k là số nút trong hàng nhị thức. 
 int empty 
 Binomial_Queue merge(ref Binomial_Queue H1, ref Binomial_Queue H2) 
 protected: 
 int count // Tổng số nút trong tất cả các cây nhị thức. 
 Binomial_Tree Trees[MAX] 
end class 
Binomial_Tree Binomial_Tree::CombineTrees(ref Binomial_Tree T1, 
ref Binomial_Tree T2); 
/* 
pre: T1 và T2 khác rỗng. 
post: T1 chứa kết quả kết hợp hai cây T1 và T2, T2 rỗng. Trả về cây T1. 
*/ 
{ 
1. if (T1.root->data > T2.root->data) 
1. Tráo T1 và T2 cho nhau 
2. T2.root->nextSibling = T1.root->leftChild // Chèn cây T2 vào đầu danh 
// sách các cây con của gốc của T1 
3. T1.root->leftChild = T2.root // Cập nhật nút con trái cho nút gốc của T1 
4. T2.root = NULL 
5. return T1 
} 
14 
16 26 
18 
12 
24 21 
65 
12 
24 21 
65 
14 
16 26 
18 
Chương 11 – Hàng ưu tiên 
Giáo trình Cấu trúc dữ liệu và Giải thuật 302
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
Binomial_Queue Binomial_Queue::merge(ref Binomial_Queue H1, 
ref Binomial_Queue H2) 
/* 
post: H1 chứa kết quả trộn hai hàng nhị thức H1 và H2, H2 rỗng. Trả về hàng H1. 
uses: hàm Binomial_Tree::notEmpty() trả về 1 nếu cây không rỗng, ngược lại trả về 0. 
*/ 
{ 
 Binomial_Tree T1, T2, carry 
 int i = 0 
1. H1.count = H1.count + H2.count 
2. loop (H2 chưa rỗng hoặc carry không rỗng) 
1. T1 = H1.Trees[i] 
2. T2 = H2.Trees[i] 
3. case (T1.notEmpty() + 2*T2.notEmpty() + 4*carry.notEmpty()) 
1. case 0: // Không có cây nào 
2. case 1: // Chỉ có cây T1 
1. break 
3. case 2: // Chỉ có cây T2 
1. H1.Trees[i] = T2 
2. H2.Trees[i].root = NULL 
3. break 
4. case 4: // Chỉ có cây carry 
1. H1.Trees[i] = carry 
2. carry.root = NULL 
3. break 
5. case 3: // Có cây T1 và T2 
1. carry = combineTrees(T1, T2) 
2. H1.Trees[i].root = NULL 
3. H2.Trees[i].root = NULL 
4. break 
6. case 5: // Có cây T1 và carry 
1. carry = combineTrees(T1, carry) 
2. H1.Trees[i].root = NULL 
3. break 
7. case 6:// Có cây T2 và carry 
1. carry = combineTrees(T2, carry) 
2. H2.Trees[i].root = NULL 
3. break 
8. case 7:// Có cả 3 cây T1, T2, và carry 
1. H1.Trees[i] = carry 
2. carry = combineTrees(T1, T2) 
3. H2.Trees[i].root = NULL 
4. break 
4. endcase 
5. i = i + 1 
3. endloop 
4. return H1 
} 
Chương 11 – Hàng ưu tiên 
Giáo trình Cấu trúc dữ liệu và Giải thuật 303
Tóm lại, trong chương này chúng ta đã xem xét một số cách hiện thực của 
hàng ưu tiên. Heap nhị phân vừa đơn giản vừa hiệu quả vì không sử dụng con trỏ, 
nó chỉ hơi tốn nhiều vùng nhớ chưa sử dụng đến mà thôi. Chúng ta đã nghiên cứu 
thêm tác vụ trộn và bổ sung thêm ba phương án khác của hàng ưu tiên. Heap lệch 
trái là một ví dụ khá hay về giải thuật đệ quy. Skew heap giống heap lệch trái 
nhưng đơn giản hơn, với hy vọng rằng các ứng dụng có tính ngẫu nhiên thì các 
trường hợp xấu nhất sẽ không thường xuyên xảy ra. Cuối cùng hàng nhị thức cho 
thấy một ý tưởng đơn giản mà lại giới hạn được chi phí cho giải thuật khá tốt. 
Binomial_Queue::Binomial_Queue(Binomial_Node* p, int k) 
/* 
pre: p là địa chỉ nút đầu tiên của một cấu trúc liên kết các cây nhị thức Bk,Bk-1,,B0. 
post: Hàng nhị thức mới được tạo thành từ các cây này. 
*/ 
{ 
1. count = (1 << (k+1)) –1 
2. loop (k >= 0) 
1. Trees[k] = p 
2. p = p->nextSibling 
3. Trees[k]->nextSibling = NULL// Cắt rời các cây con để đưa vào mảng liên 
// tục các cây nhị thức cho hàng nhị thức mới. 
4. k = k – 1 
3. endloop 
} 
Chương 11 – Hàng ưu tiên 
Giáo trình Cấu trúc dữ liệu và Giải thuật 304