Tamamen işlevsel standart bir ikili yığının herhangi bir uygulaması var mı? Biliyorum ki ilginç yığınlar var, örneğin: Binomial, sol yığın, hepsi işlevsel bir uygulamaya sahip, sadece standart ikili yığınları uygulamak için bir yol var mı, yoksa immutable tipinden dolayı bunu uygulamak için Array kullanmak zorunda mıyız? Teşekkürler!Tamamen işlevsel bir standart ikili yığın (ocaml veya haskell) nasıl uygularım?
Yığını uygulamak için bir diziye ihtiyacınız yoktur, bunu bir ağaç yapısı olarak uygulayabilirsiniz.
data Heap t = Node t (Heap t) (Heap t) | Nil
dezavantajı
her yığın işlemi için düğümlerinO(log N) yeniden tahsis kadar sonudur ve bir zorunluluk dizi tabanlı uygulama önbellek mevkiinde hiçbirine sahip olmayacaktır. Bu işlemle bazı işlemler zor olacaktır, ancak yığınla ne yapmak istediğinizi bilmediğimden, size daha spesifik bir yön gösteremem. Biz parmak ağaçlar gibi özel fonksiyonel yapılara sahip
nedeni normalde en soldaki yaprak düğümü alınırken gibi yığınları üzerinde yapmazlar belirli işlemleri hızlandırmak için olduğunu. Haskell'deki zorunlu diller için öğrendiğiniz aynı veri yapılarının çoğunu yalnızca güncellenen yöntemlerle değiştirerek kullanabilirsiniz.
Teşekkürler Dietrich, uygulamak istediğim operasyon, bu operasyonu işlevsel bir tarzda uygulamak için en iyi yolun hangisi olduğundan emin değil, kökten rastgele yeni bir değer aşağı itiyor. – Ang
Shameless fiş: Braun trees tamamen işlevsel bir dakika-yığın (veya öncelik sırasına) için mükemmel adaydırlar.
Bu yazıda A Functional Approach to Standard Binary Heaps veya bu kaynaktan Heap.scala açıklanan fikirler bakabilirsiniz.
Bu gerçekten bir soru değil. Muhtemelen, "Tamamen işlevsel bir ikili yığını nasıl uygulayabilirim?" Gibi bir şey olarak yeniden düşünmelisiniz - bu formülasyonla ilgili yararlı ve anlayışlı cevaplar almanız daha olasıdır. –
@TikhonJelvis teşekkürler – Ang
Bu bağlıdır. Tamamen işlevsel versiyonun veri için aynı yapı türünü kullanmasını bekliyor musunuz? Belirli operasyonlar için aynı şekilde davranın mı? Bu şeylerin farklı olmasına izin verilirse, gerçekten "ikili yığın" olarak adlandırılabilir mi? –