12

標準ライブラリのあまり知られていない部分を閲覧しているときに、偶然std::sort_heap. しかし、 という名前のフリー関数があるため、なぜそれが存在するのかわかりませんstd::sort。

また、複雑さは同じであることに注意してください。

だから、私の質問は: が存在する理由はsort_heap何ですか?

4

5 に答える 5

12

sort_heap入力が既にheapの形式であると仮定します。std::sortこれは、入力の順序にいくつかの制約があるため、理論的には よりも効率的に機能することを意味します (std::sortすべての入力に対して機能する必要がある とは異なります)。

コメントで述べたように、これらのパフォーマンス上の利点は決して保証されておらず、明らかに入力データに依存していることに注意する価値があります。そのため、パフォーマンスが重要な場合、プロファイリングを回避する方法はありません。

于 2012-10-08T17:31:22.243 に答える
4

データが既にヒープ プロパティを持っている場合、プロパティのないデータには適用されない明らかな並べ替えアルゴリズムがあります。つまり、ヒープの最大要素を繰り返し削除し、ヒープ プロパティを復元します。これがヒープソートの仕組みです (最初にデータをヒープ化してから、ヒープ プロパティを使用してソートします)。

したがって、ヒープがあり、それをソートしたいとします。を呼び出すこともできますがstd::sort、std::sort_heapこのアルゴリズムが使用されることを示唆するために存在します[*]。並べ替えのパフォーマンスを向上させる可能性のある手段をプログラマーに提供することは、少なくともある程度は理にかなっています。それが実際に速いかどうかは別の問題です。

ヒープソートstd:sortとしての実装が許可されていることに注意してください。

sort_heap同じ動作を取得する別の方法があるため、使用できない場合は世界がpop_heap続きます。元のヒープのより小さな初期セグメントを繰り返し呼び出します。したがって、それが面倒なら、純粋な便利な関数と見なしてください。sort_heapただし、これよりも少し良くするために、適用できる最適化がある可能性があります。

C++03 の作成者の考え方に影響を与えた可能性のある歴史的なメモ: SGI バージョンの STL では、sortintrosort を使用するようpartial_sortに定義され、heapsort を使用するように定義されていました。ただし、それが標準に含める理由とはまったく違うと思います。ヒープアルゴリズムに含めるのは「明らかな」関数でもあります。

sort_heap[*] の複雑さの要件は、「O(N log N) の比較」ではなく、「最大で N log N の比較」であるため、かなり強力なヒントです。そのため、入力データにヒープ プロパティがある場合、独自の実装が最大でその数の比較を実行することがわかっていない限り、実装はsort_heap呼び出しを持つことができません。sortsort

于 2012-10-08T18:00:21.617 に答える
0

取得元：http ：//www.sgi.com/tech/stl/sort_heap.html

sort_heapは、ヒープ[1] [最初、最後）をソートされた範囲に変換します。これは安定した並べ替えではないことに注意してください。同等の要素の相対的な順序が保持されるとは限りません。

std :: sortは、実装に基づいて最悪の場合O（N ^ 2）の複雑さを提供し、ソートされていないデータセットで機能する可能性があります。std :: sort_heapはヒープ上で機能し、常にO（nlogn）を提供します

于 2012-10-08T17:29:06.923 に答える