C ++でヒープを処理する方法

c++ heap stl
C ++でヒープを処理する方法

これはおそらく「試してみるだけ」のような質問の1つであることはわかっていますが、実際のテストデータはまだ入手できないので、コードを設計している間に経験について意見を聞きたいと思います。 。

いくつかの機能が追加された優先度キューを実装するデータ構造があります。 私が通常しなければならないことは、一度にたくさんのオブジェクトをこのヒープに追加することです。 ヒープの不変量を維持するために、 `std

make_heap()、 `std :: push_heap()、および `std :: pop_heap()`アルゴリズムを使用しています。

今のところ、挿入を行うたびに、 `std

push_heap()`を使用して単一の要素を追加します。 今、 `std :: vector :: push_back()`メソッドを使用して一度にすべての要素を追加してから、ヒープを再編成することを考えています。 現時点での単純な `push_heap()`はおそらく動作しないので、新しい `make_heap()`を使用する必要があります。 しかし、 `make_heap()`は `(3 *(last-first))`で実行されますが、 `push_heap()`は `log(last-first)`のみを取ります。

この場合、どれが実際に速いかを知る簡単な方法はありますか、またはテストデータが利用可能になるまで待つ必要がありますか?

  3  0


ベストアンサー

make_heap`は3N以下の比較(Nはヒープのサイズ)で実行されますが、 push_heap`はlog N以下で済みます。 ただし、各要素をヒープに個別にプッシュする必要があります。つまり、N個の `push_heap`を必要とするため、メソッドはN log N回の比較によって制限されます。

したがって、 make_heap`はN個の push_heap`よりも漸近的に優れています。 ヒープが初期化するのに十分な大きさである場合、そもそも問題は大きくなります。

4


_k_要素をサイズ_n_のヒープに挿入する場合、_make_heap() `は_k⋅log〜2〜(n)>3⋅n_の時点からだいたい速くなります。 つまり、_k>3⋅n/ log〜2〜(n)_の場合です。 一括挿入の前にこの値を計算してから、どのメソッドを高速化するかを決定できます。

関数の実際の実装は、おそらく操作を実行するためにこれらの時間を正確に取得しないため、この値は大まかな推定値にすぎないことに注意してください。 しかし、それは経験則として有用であり、合理的に良い結果を得るはずです。

4


タイトルとURLをコピーしました