Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 có nội dung trình bày về fibonacci heap và các ứng dụng của fibonacci heap, cấu trúc của fibonacci heap, hàm thế năng, bậc tối đa, hợp nhất hai fibonacci heap, liên kết hai gốc có cùng bậc, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | Fibonacci heap ª ÖÙng duïng cuûa Fibonacci heap Giaûi thuaät Prim ñeå xaùc ñònh moät caây khung nhoû nhaát trong moät ñoà thò coù troïng soá. Giaûi thuaät Dijkstra ñeå tìm moät ñöôøng ñi ngaén nhaát trong ñoà thò coù höôùng vaø coù troïng soá döông. Chöông 6 Fibonacci Heaps 1 Caáu truùc cuûa Fibonacci heap ª Ñònh nghóa Moät Fibonacci heap laø moät taäp caùc caây maø moãi caây ñeàu laø heap- ordered. Caây trong Fibonacci heap khoâng caàn thieát phaûi laø caây nhò thöùc. Caây trong Fibonacci heap laø coù goác nhöng khoâng coù thöù töï unordered . Chöông 6 Fibonacci Heaps 2 Caáu truùc cuûa Fibonacci heap tieáp ª Hieän thöïc Fibonacci heap trong boä nhôù Moãi nuùt x coù caùc tröôøng p x con troû ñeán nuùt cha cuûa noù. child x con troû ñeán moät con naøo ñoù trong caùc con cuûa noù. Caùc con cuûa x ñöôïc lieân keát vôùi nhau trong moät danh saùch voøng lieân keát keùp circular doubly linked list goïi laø danh saùch caùc con cuûa x. Moãi con y trong danh saùch caùc con cuûa x coù caùc con troû left y right y chæ ñeán caùc anh em beân traùi vaø beân phaûi cuûa y. Neáu y laø con duy nhaát cuûa x thì left y right y y. Chöông 6 Fibonacci Heaps 3 Caáu truùc cuûa Fibonacci heap tieáp Caùc tröôøng khaùc trong nuùt x degree x soá caùc con chöùa trong danh saùch caùc con cuûa nuùt x mark x coù trò bool laø TRUE hay FALSE chæ raèng x coù maát moät con hay khoâng keå töø laàn cuoái maø x ñöôïc laøm thaønh con cuûa moät nuùt khaùc. Chöông 6 Fibonacci Heaps 4 Caáu truùc cuûa Fibonacci heap tieáp Neáu H laø Fibonacci heap Truy caäp H baèng con troû min H ñeán nuùt goác cuûa caây chöùa khoaù nhoû nhaát goïi laø nuùt nhoû nhaát cuûa H. Neáu H laø troáng thì min H NIL. Taát caû caùc nuùt goác cuûa caùc caây trong H ñöôïc lieân keát vôùi nhau bôõi caùc con troû left vaø right cuûa chuùng thaønh moät saùch lieân keát keùp voøng goïi laø danh saùch caùc goác cuûa H. n H soá caùc nuùt hieän coù trong H. Chöông 6 Fibonacci Heaps 5 Caáu truùc
