Kodesemu untuk antrian Brodal

12

Saya mencoba untuk menemukan lebih banyak sumber daya mengenai tumpukan Brodal . Yang saya temukan hanyalah implementasi haskell dari tumpukan Brodal-Okasaki , tapi saya pikir itu tumpukan yang miring , apakah ini benar? Selain itu, saya buta huruf di Haskell sehingga tidak banyak membantu. Apakah ada yang punya (atau tahu) implementasi antrian Brodal di pseudocode, C, C ++, Python?

Harap perbaiki juga jika asumsi saya di atas salah.

research data-structures Kimvais
sumber
3
Apakah Anda ingin menerapkan antrian Brodal secara khusus, atau Anda mencari implementasi antrian prioritas yang efisien? Brodal menyebutkan dalam kesimpulan makalahnya bahwa mereka tidak praktis tanpa penelitian lebih lanjut di bidang ini. Makalahnya telah dikutip secara luas, mungkin sesuatu yang berguna? CLR Introduction to Algorithms memiliki bagian tentang antrian prioritas, tetapi referensi pekerjaan yang jauh sebelumnya dalam antrian prioritas.
Jay Elston
2
Antrian Brodal asli menggunakan tugas destruktif, sehingga versi Haskell harus memiliki beberapa modifikasi.
Fred Foo

Jawaban:

2

Implementasi Haskell didasarkan pada tumpukan Brodal-Okasaki yang fungsional dan Anda benar, ini adalah variasi tumpukan miring. Makalah ini ditulis dengan sangat jelas, jadi itu akan menjadi sumber yang bagus.

Mengenai implementasi, ada juga implementasi di Scala sebagai bagian dari perpustakaan scalaz.

maayank
sumber
1

Ini adalah jawaban parsial karena saya belum menemukan cara menerjemahkan kode menjadi sesuatu yang bukan Haskell. Alasan sejauh yang saya tahu bahwa mereka harus menggunakan Haskell adalah karena Haskell malas. Tumpukan Brodal-Okasaki perlu dipuji dengan cara malas dari koran. Jadi yang Anda perlukan adalah cara menyediakan fungsionalitas itu ke bahasa lain bersama dengan persyaratan lain (seperti struktur data yang berfungsi murni) yang mungkin dibutuhkan oleh BO Heap.

Insinyur Dunia
sumber