Minヒープ
データ構造
- 概要: 値を管理するための木構造で，データの挿入操作と最小値削除操作が共に高速に（＝ 木の高さを $h$ としたとき，$O(\log{h})$で）行えるデータ構造．
- ヒープ条件: Minヒープ $T$ は，以下の条件を満たす:
- $T$ は ほとんど完全な二分木(almost complete binary tree) である．すなわち，$T$ の高さを $h$ としたとき，$T$の葉は左詰めで木を構築しており，$T$ の任意の葉は深さが $h$ か $h-1$ である．
- $T$の任意の頂点 $u$ について，もしその子頂点 $v$ が存在するならば，$u$ の値はかならず $v$ の値以下である．
アルゴリズム
挿入処理: insert(v)
- Maxヒープ の場合とほぼ同様に定める．値の順序判定のみが異なる．
最小値削除処理: delete()
- Maxヒープ の場合とほぼ同様に定める．値の順序判定のみが異なる．