ウィキペディアのページから、最小抽出には一定の時間しかかからないため、ヒープソートを実行するためにソフトヒープを使用すると、償却されたO（n）につながるはずです。定数が大きい場合でも、非常に大きなnの場合、このアルゴリズムは非常に便利です。しかし、私はこれを言及した人は聞いたことがありません。人々がこれを使わない理由はありますか？Heapsort：パフォーマンスを向上させるために "Soft Heap"を使用してみませんか？
ありがとうございます！
ソフトヒープには「破損」（リンク先のページを参照）があり、汎用ソートルーチンのコンポーネントとして適用できません。ほとんどの場合、間違った答えを得るだけです。
ソートが必要なアプリケーションがありますが、実装の一部としてソフトヒープから取得した「破損した」結果を処理できるアプリケーションを使用している場合、潜在的なスピードアップが得られます。
フィボナッチヒープには「破損」はありませんが、O（ログn）の削除時間があります。フィボナッチヒープを汎用ソートルーチンの一部として使用できますが、ソート全体のパフォーマンスはO（n log n）になります。 @ロブのポイントにフォローアップする
：
ヒープソートが1となっているの比較に基づくソートアルゴリズムの効率の理論的限界は、があります。 No comparison-based sort can do have runtime better than Ω(n log n) in the average case。ヒープソートはΘ（n log n）なので、漸近的に最適であり、O（n）平均時変量（少なくとも比較ベースではない）が存在しないことを意味します。この議論の証拠は情報理論から来るものであり、少なくともΩ（n log n）の比較を行うことなく、入力置換と他の入力置換とを確実に区別する方法はありません。
ソフトヒープは、バイナリヒープから始めて、ソフトヒープのn個の要素の挿入と取り出しを必ずしもソートしないようにキーのいくつかの部分を破損させることによって発明されました。 （The original paper on soft heapsは、抽象的に、構造の創意工夫が、Ω（n log n）の障壁を打ち負かすために格納された値の「エントロピー」を人為的に減少させていることを述べている）。これは、ソフトヒープがO（1）タイム操作をサポートできる理由です。通常のヒープ構造とは異なり、常にソートされるわけではないため、上記の実行時バリアに拘束されません。したがって、n個のオブジェクトをO（n）時間にソフトヒープからエンキューおよびデキューできるという事実は、ヒープソートを高速化するためにソフトヒープを使用できないことを直ちに示します。
は、より一般的には、そのデータ構造を使用した場合（N Nをログ）平均的に取り組むあなたは、少なくともΩを行う場合を除きソートアルゴリズムを構築するために任意の比較ベースのデータ構造を使用する方法はありません。たとえば、this earlier questionは、バイナリヒープをO（n）時間にBSTに変換できない理由を説明しています。そうすることで、O（n）時間内に純粋に比較を使ってソートできるようになります（O（n）その後、O（n）時間内にBSTに変換し、次にソートされたシーケンスを回復するためにO（n）時間内にインオーダートラバーサルを行う）。
希望すると便利です。
@Robと@templatetypedefをありがとう！ – xuhdev
最初の段落ではΩ（n？n）にする必要がありますか？私は障壁を意味する。 – xuhdev
@ xuhdev-私はそう信じています。 Ω（n log n）は「漸近的に少なくともn log n」を意味し、すべての比較ベースソートアルゴリズムは平均的なケースで少なくともΩ（n log n）の比較を行わなければならないという障壁です。 big-O表記は* upper bound *を与え、Ωは* lower bound *を与えるので、 "少なくともO（n log n）の比較"と言うのは正しいとは言えません。それは理にかなっていますか？ – templatetypedef