Có bất kỳ triển khai nào của một vùng nhị phân chuẩn thuần túy không? Tôi biết có rất nhiều heaps thú vị như: Binomial, heap leftist, tất cả chúng đều có chức năng thực hiện, chỉ cần tự hỏi là có một cách để thực hiện heap nhị phân tiêu chuẩn hoặc chúng ta phải sử dụng Array để thực hiện nó, vì loại bất biến? Cảm ơn!Làm thế nào tôi có thể thực hiện một đống nhị phân chuẩn hoàn toàn chức năng (ocaml hoặc haskell)?
Bạn không cần một mảng để triển khai vùng heap, bạn có thể triển khai nó dưới dạng cấu trúc cây.
data Heap t = Node t (Heap t) (Heap t) | Nil
Nhược điểm là bạn kết thúc việc phân bổ lại O(log N) các nút cho mỗi hoạt động heap, và bạn sẽ không có bất kỳ địa phương bộ nhớ cache của một mảng dựa trên thực hiện mệnh lệnh. Một số hoạt động sẽ khó khăn với cấu trúc này, nhưng vì tôi không biết bạn muốn làm gì với heap, tôi không thể chỉ cho bạn một hướng cụ thể hơn.
Lý do chúng tôi có các cấu trúc chức năng đặc biệt như cây ngón tay là tăng tốc các hoạt động cụ thể mà bạn thường không thực hiện trên heap, như lấy nút lá tận cùng bên trái. Bạn có thể sử dụng nhiều cấu trúc dữ liệu giống nhau mà bạn đã học cho các ngôn ngữ mệnh lệnh trong Haskell chỉ với những thay đổi về cách thức chúng được cập nhật.
Cảm ơn Dietrich, hoạt động tôi muốn thực hiện là đẩy một giá trị mới ngẫu nhiên từ gốc, chỉ cần không chắc chắn đó là cách tốt nhất để thực hiện thao tác này theo kiểu chức năng. – Ang
Phích cắm không được biết: Braun trees là các ứng viên hoàn hảo cho một min-heap thuần túy chức năng (hoặc hàng đợi ưu tiên).
Bạn có thể xem qua các ý tưởng được mô tả trong bài báo này A Functional Approach to Standard Binary Heaps hoặc trong nguồn này Heap.scala.
Đây không thực sự là một câu hỏi. Bạn có lẽ nên viết lại nó như một cái gì đó như "Làm thế nào tôi có thể thực hiện một đống nhị phân thuần túy chức năng?" - bạn có nhiều khả năng để có được câu trả lời hữu ích, sâu sắc với công thức này. –
@TikhonJelvis cảm ơn – Ang
Điều đó tùy thuộc. Bạn có mong đợi phiên bản thuần túy để sử dụng cùng một loại cấu trúc cho dữ liệu không? Hành xử theo cùng một cách cho các hoạt động nhất định? Nếu những thứ này được phép khác, thì nó có thực sự được gọi là "đống nhị phân" không? –