tree(木)

質問

完全２分木とヒープの違いがよく分かりません。
だれか、教えてください。

回答No.2

toysmith · ベストアンサー

「rootから一番離れた末端Nodeまでの間に含まれるNodeの数」と「rootに一番近い末端Nodeまでの間に含まれるNodeの数」の差が１以内の２分木を完全２分木と言います。
完全２分木を図化した場合、非常にバランスのとれている図になります。

完全２分木の一種で、以下の条件を満たす配列
・root要素が最大値を持つ
・どの親子も「親＞子」の関係を持つ
通常の２分木は「大きい子＞親＞小さい子」の関係になりますが、ヒープでは「親より大きい子は持てない」と言うことになります。
ヒープを図化した場合、上の方に大きな値が、下の方に小さな値が集中する完全２分木となります。

お礼

ヒープは完全２分木の種類みたいなものですかね（笑）でも、ヒープだと探索が楽になるし便利ですね。ありがとうございます。

回答No.3

ymmasayan

完全２分木の説明はNo.2の方の説明のとおりですので省略します。

ヒープは完全２分木の一種で、しかも最下段は左寄せになっています。
そしてあたかも企業の組織図のように
上ほどえらい（大きい）または上ほど若い（小さい）
という構造になっています。横同士は全く気にしません。

お礼

つまり、親と子の関係のみを見ればいいのですね。
子同士はどうでもいいのか。わかりました。ありがとうございます。

回答No.1

επιστημη（@episteme）

まったく別物と考えていいでしょう。