完全二分木と二分ヒープ - プログラミング原人の進化論

今回の主題は二分ヒープです。ヒープはデータ構造の一種。メモリのヒープ領域とは異なります。

完全二分木

f:id:programgenjin:20190226201354p:plain

上の図のような二分木を完全二分木と言います。全ての葉の深さが同じで、全ての内部ノードが２つの子を持たなければなりません。

f:id:programgenjin:20190226201411p:plain

このように、葉の一部が欠けているものも完全二分木と言います（おおよそ完全二分木とも言います）。最下層の葉は左から順に埋まっており、全ての葉の深さの差が１以内でなければなりません。

二分ヒープ

ヒープは、木構造のうち、以下の条件のいずれかを満たすものを指します。

max-ヒープ条件：親のキー >= 子のキー
min-ヒープ条件；親のキー <= 子のキー

max-ヒープ条件を満たすヒープをmax-ヒープ、min-ヒープ条件を満たすヒープをmin-ヒープと呼びます。根のキーが最大のヒープがmax-ヒープ、根のキーが最小のヒープがmin-ヒープ。
二分ヒープはヒープのうち、完全二分木であるようなものを指します。二分探索木と異なり、兄弟間の大小関係に制約はありません。
ヒープは木構造ですが、配列で実装することができます。

f:id:programgenjin:20190226203557p:plain