Bài giảng Phân tích thiết kế giải thuật - Chương 5: Hệ nhị thức

0.2004 
8 
Chương 5: Heap nhị thức 
Đặc tính của cây nhị thức 
Chứng minh (tiếp) 
4. Sử dụng hình sau. 
B k - 1 
B k - 1 
B k - 2 
B 2 
B 1 
B 0 
... 
2.10.2004 
9 
Chương 5: Heap nhị thức 
Đặc tính của cây nhị thức 
Hệ luận 
	Bậc tối đa của một nút bất kỳ trong một cây nhị thức có n nút là lg n . 
2.10.2004 
10 
Chương 5: Heap nhị thức 
Định nghĩa heap nhị thức 
Định nghĩa 
Một heap nhị thức H là một tập các cây nhị thức thỏa các tính chất heap nhị thức sau 
1. Mọi cây nhị thức trong H là heap-ordered : mọi nút đều có khóa lớn hơn hay bằng khóa của nút cha của nó. 
2. Với mọi số nguyên k  0 cho trước thì có nhiều nhất một cây nhị thức trong H mà gốc của nó có bậc là k . 
2.10.2004 
11 
Chương 5: Heap nhị thức 
Tính chất của heap nhị thức 
Tính chất 
1. Gốc của một cây trong một heap nhị thức chứa khóa nhỏ nhất trong cây. 
2. Một heap nhị thức H với n nút gồm nhiều lắm là  lg n  + 1 cây nhị thức. 
Chứng minh 
1. Hiển nhiên. 
2. n có biểu diễn nhị phân duy nhất, biểu diễn này cần  lg n  + 1 
 bits, có dạng  b lg n  , b lg n  - 1 ,..., b 0  sao cho 
Cùng với định nghĩa 2, ta thấy cây nhị thức B i xuất hiện trong H nếu và chỉ nếu b i = 1. 
1 
0 
1 
0 
10 = 
3 2 1 0 
2.10.2004 
12 
Chương 5: Heap nhị thức 
Biểu diễn heap nhị thức 
một cây nhị thức 
“bên trái là con, 
bên phải là anh em” 
2.10.2004 
13 
Chương 5: Heap nhị thức 
Biểu diễn heap nhị thức 
Qui tắc trữ cho mỗi cây nhị thức trong một heap nhị thức: 
biểu diễn theo kiểu “ Bên trái là con, bên phải là anh em ” (left-child, right-sibling representation) 
Mỗi nút x có một trường sau: 
key [ x ]: trữ khóa của nút. 
Mỗi nút x có các con trỏ sau: 
p [ x ]: trữ con trỏ đến nút cha của x . 
child [ x ]: con trỏ đến con bên trái nhất của x . 
Nếu x không có con thì child [ x ] = NIL 
sibling [ x ]: con trỏ đến anh em của x ở ngay bên phải x . 
Nếu x là con bên phải nhất của cha của nó thì sibling [ x ] = NIL . 
2.10.2004 
14 
Chương 5: Heap nhị thức 
Biểu diễn heap nhị thức (tiếp) 
Ngoài ra mỗi nút x còn có một trường sau 
degree [ x ]: bậc của x (= số các con của x ) 
Các gốc của các cây nhị thức trong một heap nhị thức được tổ chức thành một danh sách liên kết, gọi là danh sách các gốc của heap nhị thức. 
Khi duyệt danh sách các gốc của một heap nhị thức thì các bậc của các gốc theo thứ tự tăng dần. 
Nếu x là một gốc thì sibling [ x ] chỉ đến gốc kế đến trong danh sách các gốc. 
Để truy cập một heap nhị thức H 
head [ H ]: con trỏ chỉ đến gốc đầu tiên trong danh sách các gốc của H . 
head [ H ] = NIL nếu H không có phần tử nào. 
2.10.2004 
15 
Chương 5: Heap nhị thức 
Tạo một heap nhị thức 
Thủ tục để tạo một heap nhị thức mới: 
M AKE -B INOMIAL -H EAP 
chiếm chổ cho và trả về một đối tượng H với head [ H ] = NIL . 
có thời gian chạy là (1). 
2.10.2004 
16 
Chương 5: Heap nhị thức 
Tìm khóa nhỏ nhất 
Thủ tục để tìm khóa nhỏ nhất trong một heap nhị thức H có n nút: 
B INOMIAL -H EAP -M INIMUM 
trả về một con trỏ đến nút có khóa nhỏ nhất. 
Thời gian chạy của thủ tục là O (lg n ) vì cần kiểm tra nhiều lắm là  lg n  + 1 nút gốc. 
B INOMIAL -H EAP -M INIMUM ( H ) 
1 y  NIL 
2 x  head [ H ] 
3 min   
4 while x  NIL 
5 do if key [ x ] < min 
6 then min  key [ x ] 
7 y  x 
8 x  sibling [ x ] 
9 return y 
2.10.2004 
17 
Chương 5: Heap nhị thức 
Liên kết hai cây nhị thức 
Thủ tục để liên kết hai cây nhị thức: 
B INOMIAL -L INK 
liên kết cây nhị thức B k - 1 có gốc tại nút y vào cây nhị thức B k - 1 có gốc tại nút z để tạo ra cây nhị thức B k . Nút z trở nên gốc của một cây B k . 
Thời gian chạy của thủ tục là O (1). 
B INOMIAL -L INK ( y , z ) 
1 p [ y ]  z 
2 sibling [ y ]  child [ z ] 
3 child [ z ]  y 
4 degree [ z ]  degree [ z ] + 1 
2.10.2004 
18 
Chương 5: Heap nhị thức 
Hòa nhập hai heap nhị thức 
Thủ tục để hòa nhập (merge) danh sách các gốc của heap nhị thức H 1 và danh sách các gốc của heap nhị thức H 2 : 
B INOMIAL -H EAP -M ERGE ( H 1 , H 2 ) 
hòa nhập các danh sách các gốc của H 1 và H 2 thành một danh sách các gốc duy nhất mà các bậc có thứ tự tăng dần. 
nếu các danh sách các gốc của H 1 và H 2 có tổng cộng là m gốc, thì thời gian chạy của thủ tục là O ( m ). 
2.10.2004 
19 
Chương 5: Heap nhị thức 
Hợp hai heap nhị thức 
Thủ tục để hợp hai heap nhị thức: 
B INOMIAL -H EAP -U NION 
hợp nhất hai heap nhị thức H 1 và H 2 và trả về heap kết quả. 
B INOMIAL -H EAP -U NION ( H 1 , H 2 ) 
1	 H  M AKE -B INOMIAL -H EAP () 
2	 head [ H ]  B INOMIAL -H EAP -M ERGE ( H 1 , H 2 ) 
3	 trả lại các đối tượng H 1 và H 2 nhưng giử lại các danh sách mà 	chúng chỉ vào 
4	 if head [ H ] = NIL 
5	 then return H 
6	 prev-x  NIL 
7	 x  head [ H ] 
8	 next-x  sibling [ x ] 
2.10.2004 
20 
Chương 5: Heap nhị thức 
Hợp hai heap nhị thức 
(tiếp) 
 9 while next-x  NIL 
10 do if ( degree [ x ]  degree [ next-x ] hay 
 ( sibling [ next-x ]  NIL 
 và degree [ sibling [ next-x ]] = degree [ x ]) 
11 then prev-x  x 	 Trường hợp 1 và 2 
12 x  next-x 	 Trường hợp 1 và 2 
13 else if key [ x ]  key [ next-x ] 
14 then sibling [ x ]  sibling [ next-x ]	 Trường hợp 3 
15 B INOMIAL -L INK ( next-x , x )	 Trường hợp 3 
16 else if prev-x = NIL 	 Trường hợp 4 
17 then head [ H ]  next-x	  Trường hợp 4 
18 else sibling [ prev-x ]  next-x	  Trường hợp 4 
19 B INOMIAL -L INK ( x , next-x )	 Trường hợp 4 
20 x  next-x	  Trường hợp 4 
21 next-x  sibling [ x ] 
22 return H 
2.10.2004 
21 
Chương 5: Heap nhị thức 
Ví dụ thực thi B INOMIAL -H EAP -U NION 
2.10.2004 
22 
Chương 5: Heap nhị thức 
Ví dụ thực thi B INOMIAL -H EAP -U NION (tiếp) 
2.10.2004 
23 
Chương 5: Heap nhị thức 
Các trường hợp xảy ra trong B INOMIAL -H EAP -U NION 
2.10.2004 
24 
Chương 5: Heap nhị thức 
Phân tích B INOMIAL -H EAP -U NION 
Thời gian chạy của B INOMIAL -H EAP -U NION là O (lg n ), với n là số nút tổng cộng trong các heaps H 1 và H 2 . Đó là vì 
Gọi n 1 là số nút của H 1 , và n 2 là số nút của H 2 , ta có n = n 1 + n 2 . 
Do đó H 1 chứa tối đa  lg n 1  + 1 nút gốc, và H 2 chứa tối đa  lg n 2  + 1 nút gốc. Vậy B INOMIAL -H EAP -M ERGE chạy trong thời gian O (lg n ). 
H chứa tối đa  lg n 1  +  lg n 2  + 2 = O (lg n ) nút ngay sau khi thực thi xong B INOMIAL -H EAP -M ERGE . Do đó vòng lặp while lặp tối đa  lg n 1  +  lg n 2  + 2 lần, mỗi lần lặp tốn O (1) thời gian. 
2.10.2004 
25 
Chương 5: Heap nhị thức 
Thủ tục để chèn một nút vào một heap nhị thức: 
B INOMIAL -H EAP -I NSERT 
chèn một nút x vào một heap nhị thức H , giả sử đã dành chổ cho x và khóa của x, key [ x ], đã được điền vào. 
Thời gian chạy của thủ tục là O (lg n ). 
Chèn một nút 
B INOMIAL -H EAP -I NSERT ( H , x ) 
1 H’  M AKE -B INOMIAL -H EAP () 
2 p [ x ]  NIL 
3 child [ x ]  NIL 
4 sibling [ x ]  NIL 
5 degree [ x ]  0 
6 head [ H’ ]  x 
7 H  B INOMIAL -H EAP -U NION ( H , H’ ) 
2.10.2004 
26 
Chương 5: Heap nhị thức 
Tách ra nút có khóa nhỏ nhất 
Thủ tục để tách ra nút có khóa nhỏ nhất khỏi heap nhị thức: 
B INOMIAL -H EAP -E XTRACT -M IN 
đem nút có khóa nhỏ nhất khỏi heap nhị thức H và trả về một con trỏ chỉ đến nút được tách ra. 
B INOMIAL -H EAP -E XTRACT -M IN ( H ) 
1 tìm trong danh sách các gốc của H gốc x có khóa nhỏ nhất, 
 và đem x ra khỏi danh sách các gốc của H 
2 H’  M AKE -B INOMIAL -H EAP () 
3 đảo ngược thứ tự của các con của x trong danh sách liên 
 kết của chúng, và gán vào head [ H’ ] con trỏ chỉ đến đầu 
 của danh sách có được 
4 H  B INOMIAL -H EAP -U NION ( H , H’ ) 
5 return x 
2.10.2004 
27 
Chương 5: Heap nhị thức 
Tách ra nút có khóa nhỏ nhất 
(tiếp) 
Thời gian chạy của thủ tục là O (lg n ) vì nếu H có n nút thì mỗi dòng từ 1 đến 4 thực thi trong thời gian O (lg n ). 
2.10.2004 
28 
Chương 5: Heap nhị thức 
Ví dụ thực thi B INOMIAL -H EAP -E XTRACT -M IN 
2.10.2004 
29 
Chương 5: Heap nhị thức 
Giảm khóa 
Thủ tục để giảm khóa của một nút trong một heap nhị thức thành một trị mới: 
B INOMIAL -H EAP -D ECREASE -K EY 
giảm khóa của một nút x trong một heap nhị thức H thành một trị mới k . 
2.10.2004 
30 
Chương 5: Heap nhị thức 
Giảm khóa 
Tính chất heap-ordered của cây chứa x phải được duy trì! 
Thời gian chạy của thủ tục là O (lg n ): vì x có độ sâu tối đa là  lg n  nên vòng lặp while (dòng 6-10) lặp tối đa  lg n  lần. 
B INOMIAL -H EAP -D ECREASE -K EY ( H , x , k ) 
 1 if k > key [ x ] 
 2 then error “khóa mới lớn hơn khóa hiện thời” 
 3 key [ x ]  k 
 4 y  x 
 5 z  p [ y ] 
 6 while z  NIL và key [ y ] < key [ z ] 
 7 do tráo key [ y ]  key [ z ] 
 8  Nếu y và z có thông tin phụ thì cũng tráo chúng 
 9 y  z 
10 z  p [ y ] 
2.10.2004 
31 
Chương 5: Heap nhị thức 
Ví dụ thực thi B INOMIAL -H EAP -D ECREASE -K EY 
2.10.2004 
32 
Chương 5: Heap nhị thức 
Xóa một khóa 
Thủ tục để xóa khóa của một nút x : 
B INOMIAL -H EAP -D ELETE 
xóa khóa của một nút x khỏi heap nhị thức H . 
Thời gian chạy của thủ tục là O (lg n ). 
B INOMIAL -H EAP -D ELETE ( H , x ) 
1 B INOMIAL -H EAP -D ECREASE -K EY ( H , x ,  ) 
2 B INOMIAL -H EAP -E XTRACT -M IN ( H ) 
2.10.2004 
33 
Chương 5: Heap nhị thức