2

私は C++ stl アルゴリズムを研究しており、ヒープ (make_heap、sort_heap、push_heap など) を理解しようとしています。私はそれが作成する二分木と、これがいつでも最も優先度の高い項目を効率的に見つけるのにどのように役立つかを理解しています. 最も価値の高いアイテムを単純に一番上にポップできるソートされたコンテナーを維持するよりも、これがどのように優れているかは私には明らかではありません。

私が見ているように、ここに比較があります：

ヒープの場合:

  • ヒープを作成します: make_heap: O(nlogn) ...間違っています! の上）
  • 挿入: push_heap: O(logn)
  • 最高を削除: pop_heap: O(logn)
  • ソートされたリストを取得: sort_heap: O(nlogn)

ソートされたコンテナの場合:

  • 初期ソート: sort() O(nlogn)
  • 挿入: ? O(ログ)
  • 最高値を削除: ポップ定数
  • ソートされたリストを取得: すでにソートされている定数

挿入には、同じ値を持つ要素、または値の両側にある 2 つの要素を見つける必要があります。ソートされたリストでは、これは O(logn) になります。これを行う特定のアルゴリズムはまだわかりません。

いずれにせよ、私は何が欠けていますか？上記の私の分析から、ソートされたコンテナーを維持することは、すべての場合において悪くはなく、場合によってはより良いことのようです。

ありがとう！

編集：

誰もこれを読んで私の質問に混乱しないように、これを指摘したいと思います。rici が指摘したように、私は make_heap の複雑さについて誤解していました。最初は O(n log n) だと思っていたのですが、O(n) でした。この違いは、ソートされたリストを単純に維持するよりも make_heap の方が優れている理由を説明しています。

4

3 に答える 3

2

並べ替えられたリストの挿入は、配列内の要素をシフトする必要があるためO(log n)、最悪のケースではありません。O(n)

于 2013-10-31T05:40:03.557 に答える
1
  1. ソート順序全体が必要ない場合があります。
  2. 最初の項目をすばやく取得し、取得時にすべてのエントリ間でソートするための計算負荷を分散させたい場合があります。すべてを前払いするのではありません。
  3. メモリに収まらないサイズのコレクションを処理したい場合があります。ヒープは、それ自体のサイズが平均 2N のソートされた実行を生成できます。この手法は、最初の実行の数が各実行の並べ替えにかかる時間を支配する場合に、並べ替えとマージのプログラムで使用されます。

このような状況では、ヒープが勝ちます。

于 2013-10-31T04:42:45.880 に答える