H16年春 ソフトウェア開発技術者 【問12】

与えられた 1 〜 8 の整数の列をヒープソートによって降順に並べ替えるため、
列の全体をヒープに構成したところ、
1、4、2、5、8、3、6、7
となった。ここで先頭の要素と最後の要素を交換して
7、4、2、5、8、3、6、1
￣￣￣￣￣￣￣￣￣￣
とし、次に下線の部分をヒープに構成する手続を実行する。このとき、実行直後の列はどうなるか。
ここで、ヒープは列の 1 番目(左端)の要素が根、列の i 番目の要素の子が 2i 番目と 2i + 1 番目の
要素と見なした完全 2 分木上に構成されるものとする。