Các heap hợp nhất được

7.3.2004Chương 5: Heap nhị thức*Các heap hợp nhất đượcMộ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.7.3.2004Chương 5: Heap nhị thức*Thời gian chạy của các thao tác lên heaps hợp nhất đượcn là số nút của heapThủ tục heap heap heap nhị phân nhị thức Fibonacci (worst-case) (worst-case) (khấu hao)MAKE-HEAP (1) (1) (1)INSERT (lg n) O(lg n) (1)MINIMUM (1) O(lg n) (1)EXTRACT-MIN (lg n) (lg n) O(lg n)UNION (n) O(lg n) (1)DECREASE-KEY (lg n) (lg n) (1)DELETE (lg n) (lg n) O(lg n)7.3.2004Chương 5: Heap nhị thức*Heap nhị thứcCác thao tác khácDECREASE-KEY(H, x, k) gán vào nút x trong heap H trị mới k của khóa, k nhỏ hơn hay bằng trị hiện thời của khóa.DELETE(H, x) xóa nút x khỏi heap H.Nhận xét:Heap nhị thức không hổ trợ thao tác SEARCH hữu hiệu.Do đó, các thao tác DECREASE-KEY và DELETE cần một con trỏ đến nút cần được xử lý.7.3.2004Chương 5: Heap nhị thức*Định nghĩa cây nhị thức7.3.2004Chương 5: Heap nhị thức*Định nghĩa cây nhị thứcCây nhị thức Bk với k = 0, 1, 2, là một cây có thứ tự được định nghĩa đệ quy:Cây nhị thức B0 gồm một nút duy nhất.Cây nhị thức Bk gồm hai cây nhị thức Bk - 1 được liên kết với nhau theo một cách nhất định:Nút gốc của cây này là con bên trái nhất của nút gốc của cây kia.7.3.2004Chương 5: Heap nhị thức*Đặc tính của cây nhị thứcLemma (Đặc tính của một cây nhị thức) Cây nhị thức Bk có các tính chất sau: 1. có 2k nút, 2. chiều cao của cây là k, 3. có đúng nút tại độ sâu i với i = 0, 1,..., k 4. bậc của nút gốc của cây là k, nó lớn hơn bậc của mọi nút khác; ngoài ra nếu các con của nút gốc được đánh số từ trái sang phải bằng k - 1, k - 2,..., 0, thì nút con i là gốc của cây con Bi .7.3.2004Chương 5: Heap nhị thức*Đặc tính của cây nhị thứcChứng minhDùng quy nạp theo k.Bước cơ bản: dễ dàng thấy các tính chất là đúng cho B0Bước quy nạp: giả sử lemma là đúng cho Bk - 1 .1. Cây nhị thức Bk gồm hai Bk - 1 nên Bk có 2k - 1 + 2k - 1 = 2k nút.2. Do cách liên kết hai cây nhị thức Bk - 1 với nhau để tạo nên Bk nên độ sâu tối đa của nút trong Bk bằng độ sâu tối đa của nút trong Bk - 1 cộng thêm 1, tức là: (k - 1) + 1 = k.7.3.2004Chương 5: Heap nhị thức*Đặc tính của cây nhị thứcChứng minh (tiếp)3. Gọi D(k, i) là số các nút tại độ sâu i của cây nhị thức Bk .Độ sâu i - 1Độ sâu iBk - 1Bk - 17.3.2004Chương 5: Heap nhị thức*Đặc tính của cây nhị thứcChứng minh (tiếp)4. Sử dụng hình sau.Bk - 1Bk - 1Bk - 2B2B1B0...7.3.2004Chương 5: Heap nhị thức*Đặc tính của cây nhị thứcHệ 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.7.3.2004Chương 5: Heap nhị thức*Định nghĩa heap nhị thứcĐịnh nghĩaMộ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 sau1. 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.7.3.2004Chương 5: Heap nhị thức*Tính chất của heap nhị thứcTính chất1. 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 minh1. 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 ,..., b0 sao choCùng với định nghĩa 2, ta thấy cây nhị thức Bi xuất hiện trong H nếu và chỉ nếu bi = 1.7.3.2004Chương 5: Heap nhị thức*Biểu diễn heap nhị thức7.3.2004Chương 5: Heap nhị thức*Biểu diễn heap nhị thứcQui tắc trữ cho mỗi cây nhị thức trong một heap nhị thức: Theo biểu diễn “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] = NILsibling[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.7.3.2004Chương 5: Heap nhị thức*Biểu diễn heap nhị thứcNgoài ra mỗi nút x còn có một trường saudegree[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 Hhead[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.7.3.2004Chương 5: Heap nhị thức*Tạo một heap nhị thứcThủ tục để tạo một heap nhị thức mới:MAKE-BINOMIAL-HEAPchiế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).7.3.2004Chương 5: Heap nhị thức*Tìm khóa nhỏ nhấtThủ tục để tìm khóa nhỏ nhất trong một heap nhị thức H có n nút:BINOMIAL-HEAP-MINIMUMtrả về một con trỏ đến nút có khóa nhỏ nhất.BINOMIAL-HEAP-MINIMUM(H)1 y  NIL2 x  head[H]3 min  4 while x  NIL5 do if key[x] 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  z10 z  p[y]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.7.3.2004Chương 5: Heap nhị thức*Ví dụ thực thi BINOMIAL-HEAP-DECREASE-KEY7.3.2004Chương 5: Heap nhị thức*Xóa một khóaThủ tục để xóa khóa của một nút x:BINOMIAL-HEAP-DELETE xóa khóa của một nút x khỏi heap nhị thức H.BINOMIAL-HEAP-DELETE(H, x)1 BINOMIAL-HEAP-DECREASE-KEY(H, x, )2 BINOMIAL-HEAP-EXTRACT-MIN(H)Thời gian chạy của thủ tục là O(lg n).