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

Không thể tạo bản xem trước, hãy bấm tải xuống
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.