C++ のヒープと優先キュー

ヒープと優先キューは C で一般的に使用されるデータ構造であり、どちらも重要なアプリケーション価値を持っています。この記事では、読者がヒープ キューと優先キューをよりよく理解して使用できるように、ヒープ キューと優先キューをそれぞれ紹介および分析します。

1. ヒープ

ヒープは、優先キューの実装に使用できる特別なツリー データ構造です。ヒープ内では、各ノードは次のプロパティを満たします。

1. その値は、その親ノードの値以上 (またはそれ以上) ではありません。
2. その左右のサブツリーもヒープです。

親ノードより小さくないヒープを「最小ヒープ」と呼び、親ノードより大きくないヒープを「最大ヒープ」と呼びます。さらに、ヒープは通常、完全なバイナリ ツリーです。つまり、ノードが左から右に配置されている最後のレベルを除いて、他のレベルのノードはいっぱいです。

C では、STL ライブラリは、ヒープを実装するための 2 つのクラス、heap および priority_queue を提供します。このうち、heap クラスは make_heap、push_heap、pop_heap などのヒープ操作関数を提供し、priority_queue クラスはヒープ実装に基づく優先キューです。次に、ヒープと priority_queue の使用状況を見てみましょう。

1. ヒープクラス

(1) ヒープの作成

ヒープを作成する前に、数値を格納するベクトル型配列を作成する必要があります。ソートされる ：

vector v = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 };

次に、make_heap を使用できます。関数からベクトル型の配列はヒープに変換されます。 int>() は、比較関数がヒープのタイプを制御できることを意味します。

(2) 要素の挿入

ヒープに要素を挿入するには、push_heap 関数を使用できます。その使用法は次のとおりです。

push_heap( v.begin(), v.end(), great());

(3) 要素の削除

ヒープ内の要素を削除するには、 Pop_heap 関数を使用すると、ヒープの先頭要素がヒープの最後の位置に移動され、要素がヒープから削除されます。この関数の使用法は次のとおりです:

pop_heap(v.begin(), v.end(), great());

v.pop_back();

priority_queue クラス

(1) ヒープの作成

ヒープ クラスとは異なり、priority_queue クラスはオブジェクトの宣言時に次のようにヒープの種類を指定できます。
2. priority_queue,greater> q;

これは、最小限のヒープを作成することを意味します。

(2) 要素の挿入

priority_queue への要素の挿入では、次に示すように、プッシュ関数を直接使用できます:

q.push(2);

q。 Push(4);

q.push(1);

q.push(9);

(3) 要素の削除

これを直接使用して要素を削除できますpriority_queue の Pop 関数は次のとおりです:

q.pop();

2. 優先キュー

優先キューは、要素をその順序に従って並べ替える特別なキューです。優先順位: 最も高い優先順位を持つ要素を並べ替えてキューの先頭に配置し、最も低い優先順位を持つ要素をキューの最後に配置します。ヒープを使用して優先キューを実装できます。

C では、priority_queue クラスはヒープに基づいて実装された優先キューであり、上記のヒープ クラスと priority_queue クラスの関数を使用して要素の挿入と削除の操作を実行できます。さらに、以下に示すように、top 関数は priority_queue クラスにも提供されており、最も高い優先度を持つ要素にアクセスするために使用されます。 );

q .push(4);

q.push(1);

q.push(9);

cout

概要:

この記事では、C のヒープと優先キューを紹介し、ヒープと優先キューの使用法と実装原則をそれぞれ分析します。この記事を学ぶことで、読者はこれら 2 つのデータ構造をより深く理解し、実際のプログラミングで柔軟に使用できるようになります。同時に、コードの正確さと効率を確保するために、読者はヒープと優先キューを使用するタイミングと注意事項に注意を払う必要があります。

以上がC++ のヒープと優先キューの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。