あ ヒープ 特別です 完全な二分木 。ヒープは完全なバイナリ ツリーであるため、ヒープは次のようになります。 N ノードには ログN 身長。優先度が最も高い要素または最も低い要素を削除すると便利です。通常、次のように表されます。 配列 。ヒープには 2 種類あります。最小ヒープ
で 最小ヒープ ルート ノードに存在するキーは、そのすべての子に存在するキー以下である必要があります。同じプロパティが、そのバイナリ ツリー内のすべてのサブツリーに対して再帰的に true でなければなりません。 Min-Heap では、ルートに存在する最小のキー要素。以下は、Min Heap のすべてのプロパティを満たすバイナリ ツリーです。
mysqlはすべてのユーザーをリストします
最大ヒープ
で 最大ヒープ ルート ノードに存在するキーは、そのすべての子に存在するキー以上である必要があります。同じプロパティである必要があります 再帰的に 真実 そのバイナリ ツリー内のすべてのサブツリーに対して。 Max-Heap では、ルートに存在する最大のキー要素。以下は、Max Heap のすべてのプロパティを満たすバイナリ ツリーです。
フルフォームpvr
最小ヒープと最大ヒープの違い
| 最小ヒープ | 最大ヒープ | |
|---|---|---|
| 1. | Min-Heap では、ルート ノードに存在するキーは、そのすべての子に存在するキー以下である必要があります。 | Max-Heap では、ルート ノードに存在するキーは、そのすべての子に存在するキー以上である必要があります。 |
| 2. | Min-Heap では、ルートに存在する最小のキー要素。 | Max-Heap では、ルートに存在する最大のキー要素。 |
| 3. | 最小ヒープでは昇順の優先順位が使用されます。 | Max-Heap では降順の優先順位が使用されます。 |
| 4. | Min-Heap の構築では、最小の要素が優先されます。 | Max-Heap の構築では、最大の要素が優先されます。 |
| 5. | Min-Heap では、最小の要素が最初にヒープからポップされます。 | Max-Heap では、最大の要素が最初にヒープからポップされます。 |
ヒープの応用 :
- ヒープソート : ヒープ ソートは、以下を使用する最良のソート アルゴリズムの 1 つです。 バイナリ ヒープ に 配列をソートする で O(N*log N) 時間。
- 優先キュー : プライオリティキューはヒープを使用して実装できます。 入れる（） 、 消去（） 、 extractMax() 、 減少キー() での操作 O(log N) 時間。
- ディクストラの最短道 そして Prim の最小スパニング ツリー 。
Min-Heap と Max-Heap のパフォーマンス分析 :
- 最大または最小の要素を取得: O(1)
- 要素を最大ヒープまたは最小ヒープに挿入: O(log N)
- 最大要素または最小要素を削除: O(log N)