なぜヒープの概念がコンテナーではなくアルゴリズム( make_heap、pop_heap、 ) として実装されているのか疑問に思っていました。私が特に興味を持っているのは、一部のソリューションが理由を説明でき、同様のアルゴリズムのコレクション (make_set add_set rm_set など) の代わりにコンテナーであるということです。push_heapsort_heapsetmap
3594 次
5 に答える
11
STL は、std::priority_queue の形式でヒープを提供します。make_heap などの関数は、データ構造自体の領域外で使用され (ソートなど)、ヒープをカスタム構造 (「上位 10 を保持する」ためのスタック配列など) の上に構築できるようにするために存在します。容器）。
同様に、std::set を使用して並べ替えられたリストを格納したり、std::adjacent_find; を使用してベクターで std::sort を使用したりできます。std::sort はより汎用的であり、基礎となるデータ構造についてほとんど仮定を行いません。
(注として、std::priority_queue 実装は実際には独自のストレージを提供しません。デフォルトでは、バッキング ストアとして std::vector を作成します。)
于 2010-06-30T18:24:15.867 に答える
5
明らかな理由の 1 つは、要素を別のコンテナー内のヒープとして配置できることです。したがって、またはC 配列
を呼び出すことができます。make_heap()vectordeque
于 2010-06-30T18:08:55.837 に答える
4
ヒープは特定のデータ構造です。標準コンテナには複雑さの要件がありますが、実装方法は指定されていません。それは立派ですが、重要な違いです。make_heap自分で作成したものを含む、いくつかの異なるコンテナーで実行できます。しかし、データを整理する方法set以上mapの意味があります。
別の言い方をすれば、標準コンテナはその基礎となるデータ構造以上のものです。
于 2010-06-30T18:12:09.810 に答える
4
ヒープ* は、ほとんどの場合、基になるデータ構造として配列を使用して実装されます。そのため、配列データ構造を操作する一連のアルゴリズムと見なすことができます。これは、ヒープを実装するときに STL がたどったパスです。これは、ランダム アクセス イテレータ (標準配列、ベクター、deque など) を持つ任意のデータ構造で動作します。
また、STL の priority_queue にはコンテナー (デフォルトではベクター) が必要であることにも気付くでしょう。これは基本的にヒープ コンテナーです。これは、基になるデータ構造にヒープを実装し、すべての典型的なヒープ操作にラッパー コンテナーを提供します。
*特にバイナリヒープ。他の形式のヒープ (Binomial、Fibonacci など) はそうではありません。
于 2010-06-30T18:12:15.110 に答える
1
ヒープは、セットやマップと同じ意味での一般的なコンテナーではありません。通常、ヒープを使用して他の抽象データ型を実装します。(最も明白なのはプライオリティ キューです。) これが異なる処理の理由であると思われます。
于 2010-06-30T18:06:30.863 に答える