誰かがSTLヒープ関数テンプレートのポイントを教えてもらえますstd::make_heapか？なぜ誰もがそれらを使用するのでしょうか？実用はありますか？
26611 次
7 に答える
48
あなたの直接の質問は、アルゴリズムとデータ構造のクラスによってよく答えられます。ヒープは、コンピュータサイエンスのアルゴリズムの至る所で使用されています。以下にリンクされているmake_heap関数から引用すると、「ヒープは、各ノードがそれ自体の値以下の値にリンクしているツリーです」。ヒープ用のアプリケーションはたくさんありますが、私が最も頻繁に使用するのは、N個の値のソートされたリストを効率的に追跡したい場合の検索問題です。
STLヒープ関数に最初に遭遇したとき、私はあなたと同じような混乱を覚えました。私の質問は少し違いました。「STLヒープがstd::vectorと同じクラスのデータ構造にないのはなぜですか？」私はそれがこのように機能するはずだと思いました：
std::heap< int > my_heap;
my_heap.heap_insert( 7 );
my_heap.heap_insert( 3 );
ただし、STLヒープ関数の背後にある考え方は、std::vectorを含むいくつかの異なる基礎となるSTLコンテナーからヒープデータ構造を作成できるようにすることです。これは、プログラムの他の場所で使用するためにコンテナーを回したい場合に非常に便利です。std :: vector以外のものを使用することを選択した場合は、ヒープの基になるコンテナを選択できるので、これも少し便利です。本当に必要なのは次のとおりです。
template <class RandomAccessIterator>
void make_heap ( RandomAccessIterator first, RandomAccessIterator last );
これは、多くの異なるコンテナをヒープにすることができることを意味します。コンパレータはメソッドシグネチャでもオプションです。make_heap関数のSTLページで試すことができるさまざまなことについて詳しく読むことができます。
リンク：
于 2009-06-03T22:17:13.313 に答える
21
リストから優先キューを作成したい場合は、make_heap を使用できます。
内部的には、ヒープは各ノードが自身の値以下の値にリンクするツリーです。make_heap によって生成されたヒープでは、メモリを消費するリンクによって決定されるのではなく、ツリー内の要素の特定の位置は、シーケンス内の絶対位置によって決定されます。*first は常にヒープ内の最大値です。
ヒープは、そのヒープ プロパティを保持する関数 push_heap および pop_heap を使用して、対数時間で要素を追加または削除できます。
于 2009-06-03T21:41:52.087 に答える
9
ベクトルまたは配列の上にバイナリヒープをstd::make_heap()一緒std::push_heap()に使用し、維持することになっています。std::pop_heap()後者の2つの関数は、ヒープを不変に維持します。std::heap_sort()このようなヒープをソートするために使用することもできます。優先キューに使用できるのは事実ですがstd::priority_queue、優先キューの内部に到達することはできません。これはおそらくあなたがやりたいことです。また、std::make_heap()一緒std::heap_sort()にC++でヒープソートを実行する非常に簡単な方法を作成します。
于 2009-06-04T06:21:24.067 に答える
8
std::make_heap実際にはほとんど使用しないでください。ヒープがプライオリティ キューに役立つことは事実ですが、構造を手動で維持する必要がある理由は説明できません。std::priority_queue優先キューだけが必要な場合は、はるかに便利なインターフェイスがあります。
とその兄弟を直接使用する場合make_heapは、基になるコンテナーに変更を加えるたびにそれらを使用する必要があります。私はそれらが2、3回使用されているのを見てきましたが、毎回間違って使用されていました.
ベクトルを優先キューとしてしばらく使用してからソートする必要があったため、ヒープ操作を直接使用したのは一度だけです。ほとんどの場合、必要になることはありませんstd::make_heap。
エレメントを変更できるプライオリティ キューが必要な場合は、 を使用できますstd::set。*s.begin()またはでそれぞれ最小または最大の要素を取得し*s.rbegin()、古い値を削除して新しい値を挿入することで要素を更新できます。
于 2011-04-09T13:52:06.700 に答える
7
[バイナリ] ヒープを構築するには、基本的に 2 つの方法があります。空のヒープを作成して各要素を一度に 1 つずつ挿入する方法と、値の範囲を取得してそれらをヒープ化する方法です。
ヒープでの各プッシュ操作には O(logn) 時間がかかるため、N 個のアイテムをヒープにプッシュする場合、O(NlogN) 時間かかります。ただし、値の配列からバイナリ ヒープを構築するには、O(N) 時間しかかかりません。
したがって、挿入中にヒープ構造を維持するよりも、各要素を配列 (またはランダム アクセス イテレータをサポートする他のコンテナー) に挿入してから、その配列に対して make_heap() を呼び出す方が理にかなっています。
于 2009-06-04T20:56:22.867 に答える
4
上記に加えて、STL のソート アルゴリズムはintrosortです。これは、クイック ソートとヒープ ソートを組み合わせたものです (クイック ソートがうまくいかない場合は、クイック ソートからヒープ ソートにフェイルオーバーします)。make_heap は、イントロソートに必要なヒープソートを実行するために必要なヒープ構造を作成します。
于 2009-06-03T21:50:24.490 に答える