ノードの位置を配列で検索する（バイナリヒープとして）

Question

ノードをバイナリヒープに挿入すると仮定して、挿入およびヒープ化後のヒープを表す配列のノードのインデックスを見つけるにはどうすればよいですか？ は、私は（Oでこのアルゴリズムを見つける必要があるログ（ログ（N））。

はあなたのすべてをありがとう。あなたは、バイナリヒープに挿入見れば

Answer 1

、新しいノードが最後に置かれ、

したがって、ヒープのサイズを知っているので、新しいノードがどのブランチに挿入されるかを知っています。ブランチサイズはlog（n）です。この位置から

このブランチに沿ったバイナリ検索だけで済むので、このブランチに属するすべてのノードを見つけることができます。 log（log（n））内の新しいノードのエース。