宿題で困っています。C++ でヒープを使用してプライオリティ キューを実装するように依頼されました。
ヒープを作成するためのコード例を検索しているときに、この定義に何度も遭遇しました。
ヒープを表す配列Aは、次の 2 つの属性を持つ配列です。
– length、配列内の要素の数
– heap-size、配列に格納されているヒープ要素の数
だから私の質問はこれです: Aとは何ですか? 自分で実装する必要がありますか (要素の配列、長さ、heap_size の 3 つのフィールドを保持するクラス ヒープを作成するとします)。
どうやって始めたらいいのかわからない。
バイナリ ヒープ データ構造は通常、特定のプロパティを持つバイナリ ツリーとして描画されますが、通常はプレーンな配列を使用して実装されます。その理由は、配列バージョンは明示的なバイナリ ツリーよりもメモリの使用量が少なく、操作がはるかに簡単だからです。したがって、説明されている配列Aは、ヒープ内のすべての値を保持する配列です。
表示されている 2 つのフィールドは、その配列の生の合計サイズ ( length ) を表し、使用可能なストレージ容量と、実際に使用しているその配列内の要素の数 ( heap-size ) を追跡します。要素をヒープに挿入するときは、そのためのスペースが存在することを確認する必要があります。配列を再割り当てして既存の要素をコピーする可能性があります。次に、バブルアップ操作を実行して新しい要素を挿入する必要があります。ヒープに。
std::vectorただし、通常は、C++や Javaなどの動的配列の上にヒープを重ねることで、配列とこれら 2 つのフィールドを維持するためのロジックを回避しますArrayList。こうすることで、ストレージ スペースを追跡し、アレイを拡張するロジックが自動的に処理されます。
割り当てパラメーターによっては、これは C++ で行われているため、ヘッダーからstd::make_heap、std::push_heap、およびstd::pop_heapアルゴリズムを調べることができます。<algorithm>のような既存のコンテナの上にヒープを実装するのが非常に簡単になりますstd::vector。実際、これはstd::priority_queueクラスが通常どのように実装されるかです。
ヒープ操作を自分で実装する必要がある場合は、この割り当てハンドアウト に記載されているバイナリ ヒープの説明を確認することをお勧めします。これは、与えられた割り当てとほぼ一致しているようです。
お役に立てれば！