ヒープ

ヒープは、値を含む「ノード」で構成されたデータ構造です。一般的なヒープでは、最上部にルートノードがあり、そのすぐ下に2つ以上の子ノードを持つことがあります。各ノードは2つ以上の子ノードを持つことができるため、子ノードが増えるたびにヒープは横に広がります。図で表すと、ヒープは上下を逆にした木のように見え、全体の形も山のようになります。

ヒープ内の各ノードは2つ以上の子ノード（「子」とも呼ばれます）を持つことがありますが、ほとんどのヒープでは各ノードの子を2つに制限します。この種類のヒープは二進ヒープとも呼ばれ、並べ替えられたデータの保存に使用できます。たとえば、「二進最大ヒープ」では、ルートノードに最大の値を保存します。2番目と3番目に大きい値は、ルートノードの子ノードに保存されます。木全体を通して、各ノードはどちらの子ノードよりも大きな値を持ちます。「二進最小ヒープ」はその反対で、ルートノードに最小の値を保存し、各ノードは子ノードよりも小さい値を持ちます。

コンピューターサイエンスでは、ヒープは単純な図として描かれることがよくあります。しかし、実際にデータをヒープに保存する処理は、より複雑です。ヒープを作成するには、プログラマーはアルゴリズムを個別に記述して、データの挿入や削除を行う必要があります。ヒープに挿入された値は通常、プログラムから参照できる配列に保存されます。ヒープ内のデータはすでに並べ替えられているため、特定の値を効率よく検索できます。

NOTE: 「ヒープ」は、動的に割り当てられたメモリを表すために使われるプログラミング用語でもあります。このメモリ領域には、実行中のアプリケーションからアクセスできます。ヒープ内のメモリは動的に割り当てられるため、使用中のメモリ量に応じて拡大または縮小します。