Tôi đã xem xét các loại cấu trúc dữ liệu heap khác nhau.Có cách triển khai Java chuẩn của một vùng Fibonacci không?
Dãy Fibonacci dường như có độ phức tạp trường hợp xấu nhất tốt hơn cho (1) chèn, (2) xóa và (2) tìm phần tử tối thiểu.
Tôi đã thấy rằng trong Java có một lớp PriorityQueue là một đống nhị phân cân bằng. Nhưng tại sao họ không sử dụng một đống Fibonacci?
Ngoài ra, có thực hiện một đoạn Fibonacci trong java.util không?
Cảm ơn!
Không, API bộ sưu tập Java tiêu chuẩn không chứa triển khai vùng Fibonacci. Tôi không chắc chắn tại sao điều này là, nhưng tôi tin rằng đó là bởi vì trong khi Fibonacci heaps là tiệm cận tuyệt vời trong một cảm giác amortized, họ có các yếu tố liên tục rất lớn trong thực tế. Khung bộ sưu tập cũng không có một đống nhị thức, đó sẽ là một đống tốt để đưa vào.
Là một plugin tự hoàn toàn không biết xấu hổ, tôi có an implementation of a Fibonacci heap in Java on my personal website. Tôi không chắc nó hữu ích như thế nào, nhưng nếu bạn tò mò muốn xem nó hoạt động như thế nào, tôi nghĩ đó có thể là một điểm khởi đầu tốt.
Hy vọng điều này sẽ hữu ích!
Nhưng tại sao họ không sử dụng vùng đệm Fibonacci?
Có lẽ vì những đống đó có nhiều chi phí cho mỗi lần nhập hơn khóa nhị phân.
Ngoài ra, có triển khai lỗ Fibonacci trong Java.util không?
Không, nhưng
Nhưng tại sao họ không sử dụng vùng đệm Fibonacci?
Tôi nghĩ nguyên nhân chính là do vùng đệm Fibonacci chỉ có thể trợ giúp trong trường hợp bạn có nhiều thao tác giảm hơn nữa được kết nối với một thao tác trích xuất. Ví dụ, khi bạn đang sử dụng nó với thuật toán của Dijkstra.
Ngoài ra, có triển khai lỗ Fibonacci trong Java.util không?
Không có triển khai thực hiện trong Java.util, nhưng tôi đã thực hiện một số thử nghiệm về chủ đề này bằng cách sử dụng các phiên bản mã nguồn mở hiện tại của vùng Fibonacci. Bạn có thể tìm thấy nó on my blog hoặc trên project's GitHub repository.
Bạn có thể xây dựng câu trả lời cho câu hỏi đầu tiên – arunmoezhi
Tất nhiên là tôi có thể. Fibonacci Heap có ưu thế hơn Binary Heap khi thực thi các thao tác reduceKey và insert, cũng có độ phức tạp tương tự với extractMin, nhưng hoạt động này tốn nhiều thời gian hơn cho FH so với BH, vì nó củng cố rừng cây bên trong. Vì vậy, nếu bạn có một vài phím giảm thì nó sẽ chậm hơn Binary Heap bình thường. Đối với một số đồ thị đặc biệt, đó là trường hợp của thuật toán Dijkstra. – gabormakrai
bộ sưu tập java chỉ cung cấp cấu trúc dữ liệu phổ biến nhất. Tôi cho rằng Fibonacci heap là chuyên biệt hơn, hoặc có lẽ nó đang sử dụng nhiều bộ nhớ hơn. –
@James, vấn đề gì với vùng Fibonacci? o.o – ignis