F＃プライオリティキュー

Question

グラフ。

いくつかの繰り返しの後、私はヒープ/優先度キューがもはやよく管理されていないことがわかります。 PriorityQueueの先頭である は、ヒープに最も低いキーを持っていません。

PQ 0 [-7230, 309] 
... 
PQ 146 [-7277, 308] 

誰もこのコードを使用していて、同様の問題が発生しましたか？ もし誰かがそれを見ているなら、私はGitHubにリンクを投稿することができます

私の必要は真ん中の要素の削除をサポートするヒープデータ構造です。 Fsharpx.collectionsはそうしたデータ構造を持っていないようです。

誰かが良い実装をどこかで知っていますか？

おかげ

Answer 1

私の答えはV.B.に触発されています。私はFSharpx.collectionsよりも別のライブラリを使用していたが、ここで、それは完全な

で、それが

Spreads

と呼ばれている詳細と手順については、そのページをお読みください。

SortedDequeは、この問題に必要なデータ構造です。 マイクロソフトのブログページコードからライブラリ関数に変更しただけで、同じコードを使用したので、良い結果が見つかったため、実際にはマイクロブログのページコード

PSにバグがあります。このスプレッドライブラリは、定量分析のために財務データをフォーマットするように設計されています。このライブラリのように見えるのはむしろ最近のことで、Googleの検索の上にない、または他のSOの質問で参照されている（または私が見たことがない場合）

FSharpx.Collectionsはこれには役に立たないあなたがその議論から見ることができるように、問題があります。heap issue in FSharpx.Collections

Answer 2

最近、私はF＃のhereにPLINQからMaxHeapを移植してのminheapそれを作りました。これは配列ベースで、 "純粋な機能"の代替品よりも優れた性能を発揮します。

しかし、多くのベンチマークの後、ちょうど単純なソートされた循環バッファに基づくSortedDequeが、私が追加したり、途中で削除する必要があっても、かなり改善されていることが分かりました。