Data-structures-algorithms-heap-data-structure
提供：Dev Guides
ヒープデータ構造
ヒープは、バランスの取れたバイナリツリーデータ構造の特殊なケースで、ルートノードキーがその子と比較され、それに応じて配置されます。 *α*に子ノード*β*がある場合-
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.
