バイナリ最大ヒープでいくつかの値Xより大きいすべてのノードを見つけるアルゴリズム

Question

ここまではこれまでのことです。

ヒープのルートから始まる再帰アルゴリズムを使用することができます（ルートが最大数であるため、Xが探しているものがルートよりも大きいかどうかを確認します）。 Xが私たちが止める根より大きい場合は、ルートを印刷して、子と右の子が残っていることを確認します...

これは良いアルゴリズムですか？私のアルゴリズムは、Nがヒープ内のノード数のNであるO（N）とする。

Answer 1

このアルゴリズムは良いです。実際には、3 * kノードを訪問するときの時間の複雑さの点で最適です。kノードの数与えられた条件を満たしている（ノードが条件を満たす場合、またはその親が行う場合にのみ訪問されるため）。

はい、最悪の場合はO(N)です。しかし、ヒープ内のすべてのノードを印刷する必要があるかもしれないので、よりうまくいくわけではありません。