基本情報試験の過去問が解けません

質問

基本情報試験の平成17年度春期の午後問題の問4の設問3について
質問があります。
なぜ回答がこのようになるのか理解ができません。。
力不足ですが、何かヒントをお願いします。
http://xn--n9q36mh1hnxuksz7wt.jp/FE17a-pm/index.html

回答No.1

irija_bari

・InitHeap は Heap Sort 開始時に Heap を作成する副プログラムです。
・InitHeap は MakeHeap を何度も呼び出すことで実現されています。

・MakeHeap は要素数が3個以下の Heap を作成するプログラムです。

以上のことから、InitHeap が木の根から木の末節に向かって MakeHeap を
行っては「だめ」なことがわかります。
（なぜなら、A[1], A[2], A[3] で MakeHeap をすると、A[1] に3要素の最大値が
入ります。
しかし、その後、A[2], A[4], A[5] で MakeHeap をすると、A[2] に A[1] よりも
大きな値が入る可能性があるからです。）

そこで、InitHeap は木の末節から木の根に向かって MakeHeap を行うことになります。
MakeHeap を行う必要のある木の節は、子の節を持つ節です。
A[x] の子の節は、 A[2*x] と A[2*x+1] です。
逆に書くと、A[x] または A[x+1] (xは偶数) の親の節は A[x/2] であるということです。

以上から、
A[Last (= x)] または、 A[Last (= x+1)] の親の節から MakeHeap を開始しなければ
ならない、 つまり、Last / 2 (小数点以下切捨て）から開始というわけです。