ヒープ

Heap ひーぷ

最頻出 ⚪ 旧用語テクノロジ系基礎理論

意味・解説

親ノードが子ノードより常に大きい（または小さい）という条件を満たす完全2分木。

最大ヒープでは親≧子、最小ヒープでは親≦子という関係を維持する。最大値または最小値を常にO(1)で取得でき、ヒープソートや優先度付きキューの実装に使われる。

会社の組織図で、上司は必ず部下より偉いというルールを守ったツリー構造（木構造）です。

【特徴】

・根には最大値（または最小値）が必ずある

・完全2分木の形を保つ

・追加・削除はO(log n)で完了

OSのタスクスケジューラは、優先度の高いプロセスを素早く取り出すためにヒープ構造を使用している。

分類: 木構造