問題タブ [soft-heap]

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

ソフト ヒープウィキペディアのページから、最小抽出には一定の時間しかかからないように見えるため、ソフト ヒープを使用してヒープソートを実行すると、償却された O(n) が発生するはずです。定数が大きい場合でも、n が非常に大きい場合、このアルゴリズムは非常に便利です。しかし、私は人々がこれについて言及しているのを聞いたことがありません。人々がこれを使用しない理由はありますか？

ありがとう！

私は最近、バーナード・チャゼルの論文「ソフト・ヒープ、バーナード・チャゼルによる最適なエラー率を持つおおよその優先度キュー」( http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap. pdf )

この論文は「腐敗」について多くのことを語っています。破損とは何ですか?要素はどのように破損するのですか?また、どのように役立ちますか?

私は論文とグーグルを読むのに多くの時間を費やしましたが、これはまだ意味がありません.

私が読んでいた論文より By Bernard chazelle https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/The%20Soft%20Heap.pdf

実際のシナリオで多く使用されているソフトヒープを見つけることができませんでした。ですから、なぜそれが本当に役立つのかを誰かが教えてくれれば助かります。