ヒープとは
配列ar[0]...ar[N-1]を考えましょう。配列は各要素が線型に並んだ集合です。ここで配列の各要素をnode（ノード/節）と呼ぶことにします。i番目のnode ar[i]に対してar[2*i+1]とar[2*i+2]の2つのnodeをar[i]の「子」、ar[i]を子nodeの「親」と呼びましょう（fig-01）。
この対応付けによって、配列の各要素はar[0]をroot（ルート/根）としてその子node、さらにその子node……のように漏れ/重複なくたどることができます（fig-02）。
つまりこの線型な要素の並びは二分木（BinaryTree）と見立てることができるわけです（fig-03）。
さて、ここで「木の中にある各節について、親は子より小さくない（親 >= 子）」という条件を与えます。この条件を満たした例を fig-04 に示します。この条件:「親は子より小さくない」を満たした木をheap（ヒープ）と呼びましょう。
ヒープに要素を追加する
fig-04で示すヒープに要素を追加する方法を考えます。このヒープの末尾、すなわち配列の末尾に要素「9」を追加しました（fig-05）。
追加した要素がその親（ここでは「7」）より大きくなければヒープの条件を満たすので要素の追加はこれで完了です。ところがここで追加した要素「9」は親より大きく、ヒープの条件を満たしません。そこで追加した要素「9」とその親「7」とを交換します（fig-06）。
処理はこれで終わりではありません。親子の交換によって親の値が変化したのですから、さらにその上の親との間でヒープ条件を満たすかを確認し、大小関係が壊れていたら（親 < 子なら）交換しなければなりません。この処理を親子の大小関係が整うまで繰り返します（fig-07）。
