tailieunhanh - Bài giảng Phân tích thiết kế giải thuật: Chương 6 - ĐH Bách khoa

Bài giảng Phân tích thiết kế giải thuật: Chương 6 - Fibonacci Heaps nêu lên cấu trúc của Fibonacci Heap; các thao tác lên Heap hợp nhất được; cây nhị thức không thứ tự; tạo một Fibonacci Heap mới; chèn một nút vào Fibonacci Heap; hợp nhất hai Fibonacci Heap;. Mời các bạn tham khảo. | Chương 6: Fibonacci Heaps Cấu trúc của Fibonacci heap Định nghĩa Một Fibonacci heap là một tập các cây mà mỗi cây đều là heap-ordered. Cây trong Fibonacci heap không cần thiết phải là cây nhị thức. Cây trong Fibonacci heap là có gốc nhưng không có thứ tự (unordered). Chương 6: Fibonacci Heaps Cấu trúc của Fibonacci heap (tiếp) Hiện thực Fibonacci heap trong bộ nhớ: Mỗi nút x có p[x]: con trỏ đến nút cha của nó. child[x]: con trỏ đến một con nào đó trong các con của nó. Các con của x được liên kết với nhau trong một danh sách vòng liên kết kép (circular, doubly linked list), gọi là danh sách các con của x. Mỗi con y trong danh sách các con của x có các con trỏ left[y], right[y] chỉ đến các anh em bên trái và bên phải của y. Nếu y là con duy nhất của x thì left[y] = right[y] = y. Chương 6: Fibonacci Heaps Cấu trúc của Fibonacci heap (tiếp) Hiện thực Fibonacci heap trong bộ nhớ (tiếp): Các trường khác trong nút x degree[x]: số các con chứa trong danh sách các con của nút x mark[x]: có trị bool là TRUE hay FALSE, chỉ rằng x có mất một con hay không kể từ lần cuối mà x được làm thành con của một nút khác. Chương 6: Fibonacci Heaps Cấu trúc của Fibonacci heap (tiếp) Hiện thực Fibonacci heap trong bộ nhớ (tiếp): Fibonacci heap H Truy cập H bằng con trỏ min[H] đến nút gốc của cây chứa khoá nhỏ nhất gọi là nút nhỏ nhất của H. Nếu H là trống thì min[H] = NIL. Tất cả các nút gốc của các cây trong H được liên kết với nhau bỡi các con trỏ left và right của chúng thành một sách liên kết kép vòng gọi là danh sách các gốc của H. n[H]: số các nút hiện có trong H. Chương 6: Fibonacci Heaps Cấu trúc của Fibonacci heap: ví dụ Chương 6: Fibonacci Heaps Hàm thế năng Dùng phương pháp thế năng để phân tích hiệu suất của các thao tác lên các Fibonacci heap. Cho một Fibonacci heap H gọi số các cây của Fibonacci heap H là t(H) gọi số các nút x được đánh dấu (mark[x] = TRUE) là m(H). Hàm thế năng của H được . | Chương 6: Fibonacci Heaps Cấu trúc của Fibonacci heap Định nghĩa Một Fibonacci heap là một tập các cây mà mỗi cây đều là heap-ordered. Cây trong Fibonacci heap không cần thiết phải là cây nhị thức. Cây trong Fibonacci heap là có gốc nhưng không có thứ tự (unordered). Chương 6: Fibonacci Heaps Cấu trúc của Fibonacci heap (tiếp) Hiện thực Fibonacci heap trong bộ nhớ: Mỗi nút x có p[x]: con trỏ đến nút cha của nó. child[x]: con trỏ đến một con nào đó trong các con của nó. Các con của x được liên kết với nhau trong một danh sách vòng liên kết kép (circular, doubly linked list), gọi là danh sách các con của x. Mỗi con y trong danh sách các con của x có các con trỏ left[y], right[y] chỉ đến các anh em bên trái và bên phải của y. Nếu y là con duy nhất của x thì left[y] = right[y] = y. Chương 6: Fibonacci Heaps Cấu trúc của Fibonacci heap (tiếp) Hiện thực Fibonacci heap trong bộ nhớ (tiếp): Các trường khác trong nút x degree[x]: số các con chứa trong