10
Có hàng đợi Fibonacci heap/priority có sẵn cho Haskell không? (? Hoặc thậm chí là một tiệm cận tốt hơn) Tôi tìm thấy một danh sách các việc triển khai hàng đợi ưu tiên khác nhau trong this question, nhưng tôi không thể tìm thấy nếu ai trong số họ đáp ứng các thời gian chạy khấu hao của đống Fibonacci:Có hàng đợi ưu tiên dựa trên Fibonacci cho Haskell không?
- Tìm-tối thiểu là O (1) thời gian khấu hao.
- Hoạt động chèn, giảm khóa và hợp nhất (công đoàn) hoạt động là O (1) thời gian khấu hao.
- Hoạt động xóa và xóa tối thiểu là O (log n) thời gian khấu hao.
Xem the comparison of theoretic bounds.
Có thể không có mã sản xuất tồn tại, vì các yếu tố không đổi thường làm cho vùng Fibonacci chậm hơn đống nhị phân cho các tập dữ liệu hợp lý, mặc dù lợi thế tiệm cận lý thuyết. –
@OliCharlesworth Thú vị, bạn có thể đưa ra một ước tính sơ bộ về những gì các kích thước Fibonacci trở nên thuận lợi? –
TBH, điều này phần nào ra khỏi khu vực của tôi; Tôi chỉ đọc về những nhược điểm đó (xem ví dụ [CLRS] (http://en.wikipedia.org/wiki/CLRS)). Đừng báo cho tôi về điều đó;) –