TAILIEUCHUNG - 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 .

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã 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.