二分木の親 C編（paizaランク C 相当）

この問題集では、プライオリティーキューを利用したダイクストラ法を扱います。プライオリティキュー（優先度付きキュー）とは、優先度の高いデータから取り出すというデータ構造で、その代表的なものがヒープといわれる木構造です。ヒープの中にも種類がありますが、今回は二分ヒープを扱います。ダイクストラ法とは、最短経路問題を解くアルゴリズムの一つです。問題集の前半で二分ヒープの実装を、後半で二分ヒープを利用したダイクストラ法の実装と利用をおこない、それぞれの理解を深めます。

まずは、二分ヒープの基本となる二分木に慣れる問題です。二分木とは、根付き木構造と呼ばれるデータ構造で、親は高々二つの子をもつという関係が成り立っています。次の画像を参考にしてください。



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

整数 N が与えられます。番号 N のノードの親ノードの番号を出力してください。

入力例 1 の場合、図から分かるように、ノード 5 の親はノード 2 となります。