data-structures - 純粋に機能的なソフトヒープ

Question

任意の言語で純粋に機能するソフトヒープデータ構造の実装はありますか?

score 20 · Accepted Answer

ACM デジタルライブラリを簡単に検索すると、Chazelle のソフトヒープ構造は非常に興味深いにもかかわらず、比較的ほとんど研究されておらず、永続的/機能的なソフトヒープは未解決の研究トピックであることがわかります。

だから私はノーと言うでしょう、永続的なソフトヒープのための既知のアプローチはありません。1つを説明することは、公開可能な結果になります（つまり、元の構造を変更する場所にコピーを追加し、共有の機会を特定することになります）.

score 1 · Accepted Answer

Haim Kaplan、Robert E. Tarjan、Uri Zwick の論文では、純粋に機能的なバリアントについて説明していますが、完全には分析していません。次の場所にあります。

score 0 · Accepted Answer

このプロジェクトには、Scala に変換するにはそれほどひどいものではないかもしれない Java コードが含まれています...そして、より機能的にします。

しかし、前述のように、Purely Functional Data Structures ブックには、特に Java コードの例を考えると、ソフトヒープに採用しやすい Haskell コードが含まれています。

data-structures - 純粋に機能的なソフト ヒープ