ポップ1 Swift編（paizaランク B 相当）

根を 0 として、各ノードに順番に番号が割り当てられた二分木を考えます。この二分木では、親ノードの番号を 2 倍して 1 または 2 を足したものが子ノードの番号となっています。

長さ 8 の数列が与えられます。この数列のインデックスと二分木の番号が対応しており、

数列の"親の番号"番目の要素は、"子の番号"番目の要素以下である

という条件(＊)が成り立っています。

今、与えられた長さ 8 の数列の先頭（0 番目）の数値が取り除かれ、数列の 0 番目には、数列の最後尾（7 番目）の値が割り当てられました。条件(＊)が成り立つように要素を入れ替えた、長さ 7 の数列を出力してください。ただし、要素の入れ替えは、二分木で親と子の関係にあるインデックス同士でのみおこなうことができるものとします。また、二つの子の要素が同じでどちらも親の要素より小さいときは、番号の小さいほうの子の要素と入れ替えをおこなってください。

入力例 1 の場合を説明します。まず次のように数列と二分木が対応しています。


ノード 0 の値が取り除かれ、ノード 7 の値 10 がノード 0 に割り当てられました。ここから入れ替えをおこなっていきます。ノード 7 には値が割り当てられなくなったので、図から省いています。


ノード 0 の値 10 は子のノード 1 の値 7 と子のノード 2 の値 3 のどちらよりも大きいので入れ替えをおこないます。ノード 2 の値 3 のほうがノード 1 の値 7 より小さいので、ノード 2 の値 3 と入れ替えます。（仮にノード 1 の値 7 と入れ替えると、値 7 がノード 2 の値 3 より大きくなるため条件(＊)が成り立ちません。）


ノード 2 の値 10 は子のノード 5 の値 9 よりも大きいので入れ替えます。



最初に数列の先頭に割り当てた値 10 が二分木の末端まで来たので、入れ替えは終了です。答えとなる、操作が終了したあとの二分木に対応する数列は以下のようになります。

3 7 9 5 12 10 11

今回の問題のように、ヒープの先頭（根）の要素を取り除く操作を一般的にポップと呼びます。ヒープでは、先頭（根）の要素が最も小さいという特徴があるため、ポップにより簡単にその最小値を得ることができます。