ヒープデータ構造

ヒープは、バランスの取れたバイナリツリーデータ構造の特殊なケースで、ルートノードキーがその子と比較され、それに応じて配置されます。 *α*に子ノード*β*がある場合-

key（α）≥key（β）

親の値が子の値より大きいため、このプロパティは Max Heap を生成します。この基準に基づいて、ヒープは2つのタイプになります-

For Input → 35 33 42 10 14 19 27 44 26 31

*Min-Heap* -ルートノードの値がその子のいずれか以下である場合。

最大ヒープの例

*Max-Heap* -ルートノードの値がその子のいずれか以上である場合。

最大ヒープの例

両方のツリーは、同じ入力と到着順序を使用して構築されます。

最大ヒープ構築アルゴリズム

同じ例を使用して、最大ヒープがどのように作成されるかを示します。最小ヒープを作成する手順は似ていますが、最大値ではなく最小値を使用します。

一度に1つの要素を挿入することにより、最大ヒープのアルゴリズムを導き出します。ヒープは常にそのプロパティを維持する必要があります。挿入中に、すでにヒープ化されたツリーにノードを挿入していることも想定しています。

Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

注-最小ヒープ構築アルゴリズムでは、親ノードの値が子ノードの値よりも小さくなると予想されます。

アニメーションの図でMax Heapの構造を理解しましょう。前に使用したのと同じ入力サンプルを検討します。

最大ヒープアニメーションの例

最大ヒープ削除アルゴリズム

最大ヒープから削除するアルゴリズムを導き出しましょう。最大（または最小）ヒープの削除は、常にルートで行われ、最大（または最小）値が削除されます。

Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

最大ヒープ削除アニメーションの例

Data-structures-algorithms-heap-data-structure

ヒープデータ構造

最大ヒープ構築アルゴリズム

最大ヒープ削除アルゴリズム