10

クイックソートは、実際にはヒープソートよりも優れています。マージソートは、3つのうち唯一の安定したものです(プレーンなバニラ実装で)。したがって、手元の状況に応じて使用されるのはクイックソートまたはマージソートのいずれかです(メモリ内のインプレースまたは外部ソーティングなど)。

では、ヒープデータ構造が実際にソートに使用される場合はありますか?私がどれだけ「グーグル」したり、アプリケーションを考え出そうとしても、ほとんどの場合、ヒープソートではなくマージ/クイックソートを選択します。私の職業生活でも、実際にヒープソートが使われているケースはありません。好奇心から、実際のヒープソートの実際の良いユースケースは何でしょうか?

4

1 に答える 1

5

私の頭の上からいくつかの利点があります(さらに調査を行った後、このリストを修正します:

  • ほとんどソートされたセットは、ヒープソートによってソートされることでメリットがあります。
  • スペースを意識した環境では、多くの場合、ヒープソートの O(1) スペースの複雑さが好まれます。組み込みシステムを考えてみてください。
  • 巨大なデータ セットは、O(nlog n)の保証された実行時間の恩恵を受けます。医療、宇宙、生命維持などを考えてみてください。
于 2012-12-30T01:25:01.040 に答える