Bài giảng Giải thuật - Chương 5: Heap nhị thức
ª Heap nhị phân
ª Một heap hợp nhất được (mergeable heap) là một cấu trúc dữ liệu hỗ trợ năm thao tác sau (gọi là các thao tác heap hợp nhất được).
– MAKE-HEAP() tạo và trả về một heap trống.
– INSERT(H, x) chèn nút x, mà trường key của nó đã được điền, vào heap H .
– MINIMUM(H) trả về một con trỏ chỉ đến nút trong heap H mà khóa của nó là nhỏ nhất.
– EXTRACT-MIN(H) tách ra nút có khóa nhỏ nhất khỏi H, và trả về một con trỏ chỉ đến nút đó.
– UNION(H1, H2) tạo và trả về một heap mới chứa tất cả các nút của các heaps H1 và H2 . Các heaps H1 và H2 sẽ bị hủy bởi thao tác này.
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
File đính kèm:
- bai_giang_giai_thuat_chuong_5_heap_nhi_thuc.ppt